본문 바로가기
반응형

분류 전체보기282

백준 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.
백준 7569번 토마토 - 스위프트(Swift) 풀이 + 그림 설명 1. 토마토를 그래프의 정점으로 생각한다. 2. BFS로 하루가 지날 때마다 인접한 토마토들을 하나씩 익혀가는 것을 구현한다. 3. 마지막에 안 익은 토마토가 있는지 확인한다. 1. 토마토를 그래프의 정점으로 생각한다. 들어있지 않은 칸은 무시하고, 토마토들을 그래프의 정점으로 생각한다. 전체 상자를 그래프로 바꾸어줄 것이다. 2. BFS로 하루가 지날 때마다 인접한 토마토들을 하나씩 익혀가는 것을 구현한다. 빨간색은 익은 토마토이고, 초록색은 안 익은 토마토를 나타내었다. 빨간색 정점에 적힌 숫자는 첫 날로부터 며칠 후에 익었는지를 기록한 것이다. 처음부터 3개의 토마토가 익어있는 아래와 같은 상황이라고 하자. 하루가 지나 1일 째가 되면, 바로 옆에 붙어있는 초록색 토마토 3개가 추가로 아래와 같이 .. 2022. 1. 18.
반응형

티스토리툴바