본문 바로가기
반응형

Problem Solving/BOJ228

백준 1043번 거짓말 - 스위프트(Swift) 풀이 1. 같은 파티에 참석하는 사람들끼리는 같은 종류(진실/거짓)를 들어야 하므로 한 집합으로 묶는다. 2. 진실을 아는 사람들을 한 집합으로 묶는다. 3. 각 파티의 참석자들이 진실을 알아야 하는 집단인지 체크한다. 1. 같은 파티에 참석하는 사람들끼리는 같은 종류(진실/거짓)를 들어야 하므로 한 집합으로 묶는다. 같은 종류를 들어야 하는 사람들을 한 집합으로 묶어 취급할 것이다. Union-Find 알고리즘을 사용해서 구현하면 된다. 같은 파티에 참석하는 사람들은 무조건 같은 종류를 들어야 한다. 따라서 한 파티 내의 참석자들을 한 집합으로 묶는다. 2. 진실을 아는 사람들을 한 집합으로 묶는다. 이제 진실을 아는 사람들도 모두 진실을 들어야 하므로 한 집합으로 묶어준다. 이렇게 되면 만약 파티 참석자 .. 2022. 1. 24.
백준 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.
반응형

티스토리툴바