목록알고리즘 (6)

Get Up & Code, MacKin Talk

[백준]11047_동전0

문항 분석 입력 제한 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 가치가 더 큰 동전으로 가치가 더 작은 동전보다 더 적은 수를 활용해 합을 만들 수 있다. 가치가 큰 동전을 매번 하나씩 반복문을 통해 뺴는 방법을 사용하면 그만큼 시간적 소요가 크므로 나누기 연산과 나머지 연산을 활용해 접근하면 될 것 같다. Code import Foundation let input = readLine()!.split(separator: " ").map{ Int(String($0)) } var coins = [Int]() let n = input[0]! var k = input..
IOS/알고리즘 문제 풀이 2021. 10. 6. 22:00
[백준]18830_좌표압축

1. 문제 분석 Xi의 값이 Xj보다 큰 좌표의 개수를 찾아야 한다.(좌표 압축) Xi를 좌표 압축한 결과 = Xi' 입력: X1, X2, ..., XN 출력: X1', X2', ..., XN' 2. 풀이 계획 입력 제한 1 ≤ N ≤ 1,000,000 -10^9 ≤ Xi ≤ 10^9 N^2으로 검증하는 순간 시간 초과는 분명. 3. 계획 검증 전체 반복문 n 개별 반복문 p 각 명령어 실행 시간 1 O(np) 4. 소스 코드 import Foundation var set = Set() var dic = [Int: Int]() _ = Int(readLine()!)! var input = readLine()!.split(separator: " ").map { Int(String($0))! } // O(N)..
IOS/알고리즘 문제 풀이 2021. 10. 6. 21:34
[백준]5430_AC

1. 문제 분석 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있음. R은 뒤집는 함수, D는 첫 번째 숫자를 버리는 함수 Error: 배열이 비어있는데 D를 사용한 경우 예제 입력: 1) Testcase 수 2) p : 수행할 함수 (String) 3) n : 배열에 들어있는 수 개수 4) [xi,...] : 수가 들어가 있는 배열 제한 조건 : Sum(P) + n tail } } import Foundation final class FileIO { private let buffer:[UInt8] private var index: Int = 0 init(fileHandle: FileHandle = FileHandle.standardInput) { buffer = Array(try! fileHand..
IOS/알고리즘 문제 풀이 2021. 10. 1. 23:59
알고리즘 문제 풀이 53번 : K진수 출력(stack)

목차 문항 분석 Code 결과 및 분석 문항 분석 10진수 N이 입력이 되었을 때, 이를 K진수로 변환해 출력하도록 하는 프로그램을 작성해야 한다. 접근 방법 : N을 입력 받았다고 했을 때, K로 나눈 나머지를 차례로 기록해 역순으로 출력하면 된다. N%K 연산을 진행할 때마다 값을 스택 구조를 활용해 차례대로 저장한 후, top부터 역순으로 출력하면 된다. 이를 저장하기 위해 입력 범위를 담을 수 있는 충분한 크기를 가진 스택을 구성했다. 스택 구조를 간단히 도식화한 그림은 다음과 같다. Code // // 53_k진수 출력.cpp // Algorithm // // Created by WANKI KIM on 2021/01/14. // #include using namespace std; ..
IOS/알고리즘 문제 풀이 2021. 1. 15. 17:16
알고리즘 문제 풀이 51번 : 영지(territory)선택:(large)

목차 문항 분석 Code 결과 및 분석 문항 분석 기존의 방법의 문제를 개선했다. 같은 문항 50번 문항에서 2차원 배열 내 일부 배열의 합을 구하기 위해서 4중 for문을 사용했다. 위 방법으로 문제를 풀 수 있지만, for문의 반복 횟수가 너무 많아지는 문제가 발생했다. 실제로 2차원 배열의 크기를 키울수록 반복횟수는 훨씬 많이 증가하는 문제를 보였다. 소위 Dynamic Programming 라고 부르는 방법을 for문의 반복 횟수를 줄이기 위한 전략으로 채택함. Code // // 51_territory(large).cpp // Algorithm // // Created by WANKI KIM on 2021/01/14. // // TODO: 사각형 격자로 이뤄진 땅에서 가장 많은 오렌지 나무가 심..
IOS/알고리즘 문제 풀이 2021. 1. 14. 18:07
알고리즘 문제 풀이 47번_봉우리 찾기

목차 문항 분석 Code 결과 및 분석 문항 분석 2차원 배열이 입력으로 들어왔을 때, 해당 Index의 부분이 해당 배열의 값을 둘러싼 다른 값보다 낮은 값을 가지는지 높은 값을 가지는지를 비교해 봉우리 여부를 판단하고, 이를 갯수로 추려내는 문항. 풀이 방향 1. 2차원 배열 생성 -> 외부에 0으로 채워진 배열을 추가로 형성해 외부 영역에 대한 추가 예외처리를 피함. 0 0 0 0 0 0 0 0 5 3 7 2 3 0 0 3 7 1 6 1 0 0 7 2 5 3 4 0 0 4 3 6 4 1 0 0 8 7 3 5 2 0 0 0 0 0 0 0 0 -> index 중 이전 탐색에서 이미 더이상 조회가 필요없는 부분을 건너뛸 필요성 있음. 같은 크기의 2차원 배열 선언 후 flag 값 사용 가능할 듯. Cod..
IOS/알고리즘 문제 풀이 2021. 1. 12. 14:24
이전 Prev 1 Next 다음