DP

문제 https://www.acmicpc.net/problem/2193 풀이 문제에서 명시적으로 두 가지 조건을 제공해준다. 0으로 시작하지 않는다. 1이 연속되지 않는다. 이진수라는 조건도 있으므로, 3가지 조건이 있다고 볼 수 있다. 케이스를 몇개 써보면 쉽게 DP로 풀 수 있는걸 알 수 있다. dp[1] = 1 // 1 dp[2] = 1 // 10 dp[3] = 2 // 100, 101 dp[4] = 3 // 1000, 1001, 1010 2번째 조건 때문에, 0으로 끝나는 경우에는 1을 붙일 수 있지만, 1로 끝나는 경우에는 0으로 붙일 수 없는 것을 알 수 있다. DP 테이블을 다음과 같이 정의하자. ...

문제 https://www.acmicpc.net/problem/12852 풀이 DP를 사용해서 해결했다. 문제를 거꾸로 뒤집어보자. n에서 1을 가는 최단거리가 아니라, 1에서 n으로 가는 최단거리로 바꾸는 편이 편하다. 이렇게 뒤집으면 개별 숫자에서 다른 숫자로 갈 수 있는 방법은 3가지가 주어진다. 1 더하기 2 곱하기 3 곱하기 쉽게 점화식을 만들 수 있다. dp[i] = max(dp[i - 1], dp[i / 2], dp[i / 3]) + 1 하지만 경로도 트래킹 해야 하는데, 이건 각 개별 숫자에 도달하기 전에 어떤 수에서 왔는지를 저장하는 배열 하나를 만들고, 최종적으로 이 배열을 루프로 순회하거나, 재귀를 통해서 경로를 얻어낼 수 있다. ...

문제 https://www.acmicpc.net/problem/2293 풀이 DP를 사용하는 문제이다. dp 테이블의 각 인덱스가 해당 인덱스 만큼의 가치를 만들 수 있는 경우의 수 라고 하면 쉽게 풀 수 있다. 동전의 가치를 value라고 하면 그 동전을 하나 추가해서 i만큼의 가치를 만들 수 있는 경우의 수는 dp[i] += dp[i - value] 라고 할 수 있다. 따라서 하나의 가치에 대해서 동전의 종류의 수 만큼 반복문을 돌려야 한다. 문제에서 주어진 또 다른 조건은 경우의 수가 2의 31제곱이 넘지 않는다는 것이다. 또한 스위프트에서는 오버플로우를 방지하기 위해 2의 31제곱이 넘어가는 수를 다 제거해줘야 한다. (최종적으로 출력할 결과가 2의 31제곱이 넘어가지 않으므로 중간에 2의 31제곱이 넘는 값은 자연스럽게 쓸모가 없는 값이 된다.) ...

문제 https://www.acmicpc.net/problem/1520 풀이 dfs를 이용하면 쉽게 풀 수 있는 문제일 것 같지만, 주어지는 그래프의 크기가 커서 시간초과가 나오는 문제이다. 하지만 이러한 문제들은 중첩되는 연산이 많으므로 DP를 이용하면 시간초과 없이 해결할 수 있는 경우가 흔하다. DP의 컨셉은 다음과 같다. 그래프의 특정 칸에서 목적지로 도착하는 경우의 수는 앞선 경로에 상관없이 항상 같다. 따라서 각 칸에서 목적지로 가는 경로의 수를 dp테이블에 메모이제이션 한다면 불필요한 연산을 하지 않아도 된다. 따라서 점화식을 dp[x][y] = dp[x - 1][y] + dp[x + 1][y] + dp[x][y - 1] + dp[x][y + 1]로 일반화 할 수 있다. 각 항에서 탐색이 불가능한 칸((x, y)보다 높은 칸, 존재하지 않는 칸) 에 대응되는 항은 제외해야하기 때문에 엄밀히 말해서는 틀리지만, 이해하는데는 충분하다. ...

문제 https://www.acmicpc.net/problem/14003 풀이 LIS(Longest Increasing Subsequence)라고 하는 유명한 DP 문제이다. 이 문제 외에도 연계된 문제들이 많으니 1번(BOJ 11053)부터 차례대로 풀면 어느새 여기까지 풀게 된다. 이 문제들은 총 2가지 기준으로 분류된다. 첫 번째 기준은 O(n²), O(nlogn) 두 번째는 LIS 출력 여부이다. 이 중에 O(nlogn) 알고리즘을 사용하고 LIS를 직접 출력해야 하는 문제가 이 문제이다. 원래는 Swift로 작성하려 했지만, 백준의 입력시간 문제 때문에 Swift론 입력 횟수가 적은 O(n²)문제를 풀고 O(nlogn) 문제는 C++로 작성하였다. 기본적인 알고리즘 콘셉트는 다음과 같다. ...