본문 바로가기
반응형

Problem Solving242

백준 10830번 행렬 제곱 - 스위프트(Swift) 풀이 1. 분할 정복으로 해결한다. 2. B % 2 = 0인 경우, multiplyMatrix(B) = multiplyMatrix(B/2) * multiplyMatrix(B/2) 3. B % 2 = 1인 경우, multiplyMatrix(B) = multiplyMatrix(B/2) * multiplyMatrix(B/2) * A 4. 메모이제이션을 통해 연산 횟수를 줄인다. 5. 초기 행렬에 1000이 있는 경우를 조심한다. 1. 분할 정복으로 해결한다. 진짜로 B제곱을 하면 B가 10^12로 엄청 크기 때문에 당연히 시간 초과가 난다. 대신 유명한 알고리즘인 분할 정복을 이용한 거듭제곱을 사용한다. 2. B % 2 = 0인 경우, multiplyMatrix(B) = multiplyMatrix(B/2) * mu.. 2022. 1. 22.
백준 9465번 스티커 - 스위프트(Swift) 풀이 1. dp(n, up, down) = n번째 열의 위아래 스티커 존재 여부가 up, down일 때, n번째 열부터 끝까지 고려했을 때 얻을 수 있는 최대 점수 2. n번째 열의 위아래 스티커 모두 떼지 않는 경우의 최대 점수 = dp(n+1, 1, 1) 3. n번째 열의 위 스티커만 떼는 경우의 최대 점수 = stickers[0][n] + dp(n+1, 0, 1) 4. n번째 열의 아래 스티커만 떼는 경우의 최대 점수 = stickers[1][n] + dp(n+1, 1, 0) 5. dp(n, up, down) = max(2번 경우, 3번 경우, 4번 경우) 1. dp(n, up, down) = n번째 열의 위아래 스티커 존재 여부가 up, down일 때, n번째 열부터 끝까지 고려했을 때 얻을 수 있는 .. 2022. 1. 22.
백준 9019번 DSLR - 스위프트(Swift) 시간초과 해결 BFS를 돌면서 해당 노드까지 오게 된 경로를 기록해야 하는데, 바로 출력 가능하도록 이전 노드까지 오게 된 경로 문자열에 + 연산자를 사용해서 기록을 하니 시간 초과가 났다. 문자열에 +하는 연산은 역시 코스트가 엄청 큰가 보다. n을 2배로 만드는 D 연산이 있기 때문에 최대 연산 횟수가 logN 언저리일 것이므로 Int의 각 자릿수에 한 글자가 대응되도록 저장이 가능했다. "D", "S", "L", "R"을 각각 1, 2, 3, 4로 대응시켜 122314 = "DSSLDR"처럼 읽을 수 있도록 기록했더니 통과되었다. 마지막에 출력할 때 숫자 → 문자열로 변환하는 작업을 한번 거쳐줘야 한다. import Foundation struct Queue { var queue = [Int]() var fron.. 2022. 1. 21.
백준 6064번 카잉 달력 - 스위프트(Swift) 풀이 + 그림 설명 1. 에서 a를 x로 고정한다. → 2. a를 x로 고정하면 고려해야할 경우의 수는 N/GCD가지이다. 3. N/gcd가지 중에 b = y인 경우가 있는지 확인한다. 1. 에서 a를 x로 고정한다. → 1번째 해부터 마지막 해까지 모두 고려하면, M, N이 최대 40,000이므로 O(N^2)으로는 시간초과가 나게 된다. 둘 중에 하나를 고정해서 O(N)에 해결이 가능하도록 하자. 2. a를 x로 고정하면 고려해야할 경우의 수는 N/GCD가지이다. M = 3, N = 2인 경우를 생각해보자. 라고 하면 a자리는 1, 2, 3이 반복되고 b자리에는 1, 2가 반복된다. 따라서 M과 N의 최소공배수번째 해에 이 될 것이다. 총 LCM개의 해 중에서 a = x인 경우는 총 LCM / M가지가 될 것이다. 이때 .. 2022. 1. 21.
백준 11659번 구간 합 구하기 4 - 스위프트(Swift) 풀이 + 그림 설명 1. 첫 번째 수부터 i번째 수 까지의 합을 저장하는 누적합 배열을 만든다. psum[i] = arr[0] + arr[1] + arr[2] + ... + arr[i] 2. arr[i] ~ arr[j] 의 구간 합은 psum[j] - psum[i - 1]과 같다. 3. i = 0인 경우 예외 처리를 해준다. 1. 첫 번째 수부터 i번째 수 까지의 합을 저장하는 누적합 배열을 만든다. psum[i] = arr[0] + arr[1] + arr[2] + ... + arr[i] 구간 i부터 j까지 반복문을 돌면서 실제로 돌면 M개의 쿼리에 대해 O(N)이 걸리는 작업을 수행하므로 총 O(NM)의 시간 복잡도를 갖는다. 이 방법으로는 N과 M이 각각 최대 10^5이므로 시간초과가 날 것이다. 구간합을 O(1)에 구.. 2022. 1. 19.
반응형

티스토리툴바