동적계획법이란 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법을 뜻합니다.
점화식(작은 문제와 큰 문제간의 관계식)을 기반으로 하는 방법이며, for문을 이용하여 해결할 수도 있고, 재귀함수를 이용하는 것도 가능합니다.
2. Memoization (Top-Down Approach)
Memoization의 정의
재귀함수를 이용하여 문제를 해결하는 과정에서, 이미 한번 계산한 결과를 기록하여, 동일한 작업의 계산을 반복하지 않는 것입니다. 즉, 각 n에 해당하는 값을 정확히 한 번씩만 계산하게 됩니다.
이런식으로 값을 기록하고, 그 기록한 값을 참조하는 것을 메모이제이션이라고 부릅니다.
Memo 배열의 이용
memo라는 배열을 만들고, 처음에는 전부 -1로 초기화를 합니다.
memo에 해당하는 값이 -1이라면, 그 값을 실제로 계산한 뒤 memo에 저장해둡니다.
이후 memo에 해당 값이 -1이 아니라면, 이미 계산한 적이 있었다는 뜻이므로, memo에 적혀있는 값을 그대로 반환합니다.
function fibbo(n)
if memo[n] != -1 // 이미 n번째 값을 구해본 적이 있다면
return memo[n] // memo에 적혀있는 값을 반환해줍니다.
if n <= 2 // n이 2이하인 경우에는 종료 조건이므로
memo[n] = 1 // 해당하는 숫자를 memo에 넣어줍니다.
else // 종료조건이 아닌 경우에는
memo[n] = fibbo(n - 1) + fibbo(n - 2) // 점화식을 이용하여 답을 구한 뒤, 해당 값을 memo에 저장해줍니다.
return memo[n] // memo 값을 반환합니다.
memo 배열을 사용하지 않을 때는 O(2^N)의 시간복잡도를 갖지만, memo 배열을 사용하였을 때는 중복하여 탐색하는 경우가 아예 사라졌기 때문에, O(N)이 소요됩니다.
3. Tabulation (Bottom-Up Approach)
Tabulation의 정의
for문을 이용하여 문제를 해결하는 과정에서, 순서대로 배열에 값을 채워나가는 방식을 말합니다.
set dp = [0, 0, 0, ...]
dp[1] = 1
dp[2] = 1
for i = 3 ... i <= n:
dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n])
Memoization vs Tabulation
Memoization의 경우에는 높은 수에서 낮은 수(구하려는 n번째 식을 구하기 위해 n - 1, n - 2번째 값을 구하려고 하므로)로 내려가기 때문에 탑다운 방식(Top-Down Approach) 이라고 부르며, Tabulation의 경우에는 아래에서 값을 채워 나가기 때문에 바텀업 방식(Bottom-Up Approach) 이라고 부릅니다.
탑다운 방식은 재귀를 사용하고, 바텀업 방식은 반복문을 사용합니다.
이론적인 시간복잡도는 두 방법이 동일하나, 탑다운 방식은 함수를 재귀적으로 여러번 실행해야하므로, 함수 처리에 추가적인 시간이 약간 더 붙어 실제로는 바텀업 방식이 약간 더 빠릅니다. 하지만, 탑다운 방식은 모든 값을 연산하는 게 아닌 필요한 값만 연산하기 때문에, 상황에 따라 더 빠를 수도 있습니다.
4. 대표적인 DP 문제 유형
1) subproblem을 그대로 합치면 되는 DP
점화식이 여러 작은 문제의 합으로 표현되는 경우입니다. 특정 시점에 할 수 있는 선택지를 판단하고, 각 경우가 앞의 값을 어떤 식으로 참조할 수 있는지 설계하는 것이 중요합니다.
2 × N 크기의 벽을 2 × 1, 1 × 2 크기의 타일로 채울려고 합니다. N=10일 때 가능한 경우의 수는?
dp[i]를 2 x i 크기의 벽을 2 x 1, 1 x 2 크기의 타일로 채우는 데 가능한 서로 다른 가짓수라고 정의합니다.
i번째를 끝으로 2 x i벽을 전부 타일로 채우는 경우를 생각해보면, 다음과 같이 끝에 세로로 하나를 붙이거나, 끝에 가로로 2개를 붙이는 경우만 존재합니다. 세로로 하나 붙이는 경우에는 남은 2 x (i-1) 크기의 벽돌을 채우는 경우의 수와 같아지므로 dp[i-1]가지가 되며, 가로로 2개를 붙이는 경우에는 남은 2 x (i-2) 크기의 벽돌을 채우는 경우의 수와 같아지므로 dp[i-2]가 됩니다.
즉, 아래와 같이 점화식을 세울 수 있습니다. i가 0인 경우는 타일을 전혀 놓지 않는다는 의미의 1가지가 있습니다.
dp 값을 순서대로 채워놓은 후, 10번째 값을 읽으면 답(89)이 됩니다.
1부터 N까지의 숫자들을 단 한번씩만 써서 서로 다른 이진탐색트리(BST)를 만들려고 합니다. N=6일 때 만들 수 있는 서로 다른 이진탐색트리(BST)의 개수는?
dp[n]을 노드 n개로 만들 수 있는 서로 다른 BST의 개수라고 정의합니다.
BST의 경우의 수를 구하기 위해서는 루트에 어떤 숫자가 오는지에 집중(왼쪽 - 루트보다 작은 숫자, 오른쪽 - 루트보다 큰 숫자)해야합니다. n=4일때, 루트에 1부터 4까지의 숫자가 사용될 때 왼쪽과 오른쪽에 사용될 수 있는 숫자들의 집합을 생각해보면 다음과 같습니다.
이는 루트가 1일때 [2,3,4]로 BST를 만드는 경우이므로 dp[3]이 되고, 루트가 2일때 [1]로 BST를 만들며 동시에 [3,4]로 BST를 만드는 경우이므로 dp[1]*dp[2]가 되고, 루트가 3일때도 비슷하게 dp[2]*dp[1], 루트가 4일때도 비슷하게 dp[3]이 됩니다.
즉, 아래와 같이 점화식을 세울 수 있습니다. n이 0인 경우는 노드가 전혀 없다는 의미의 1가지가 있습니다.
루트가 정해졌을 때 만들 수 있는 서로 다른 BST의 개수는 (왼쪽에 들어갈 수로 만들 수 있는 서로 다른 BST의 개수) * (오른쪽에 들어갈 수로 만들 수 있는 서로 다른 BST의 개수)로 나타낼 수 있습니다.
dp 값을 순서대로 채워놓은 후, 6번째 값을 읽으면 답(132)이 됩니다.
2) 격자 안에서 한 칸씩 전진하는 DP
문제 상황에 맞는 적절한 점화식을 세우고, 해당 점화식에 맞춰 DP 테이블에 값을 순서대로 채워넣으면 문제에서 원하는 답을 구할 수 있게 됩니다.
4개의 행으로 이루어진 직각삼각형 모양으로 된 판에 숫자들이 주어졌을 때, 최상단에서 시작하여 최하단으로 이동했을 때 얻을 수 있는 최대합은? (단, 특정 위치 (r,c)에서의 이동은 (r+1,c) 혹은 (r+1, c+1) 지점으로만 가능합니다.)
dp[i][j]를 마지막으로 방문한 위치를 (i,j)라 했을 때, 얻을 수 있는 최대 합이라 정의합니다.
(i,j)에 도달하는 경우를 생각해보면, 바로 위(i-1, j)에서 내려오는 경우와 좌측 모서리(i-1, j-1)에서 내려오는 경우 2가지가 존재합니다. 이 중 더 좋은 경우를 선택해주면 됩니다.
즉, 아래와 같이 점화식을 세울 수 있습니다. 각 칸에 적혀있는 수를 a[i][j]라 생각합니다.
dp 값을 왼쪽 → 오른쪽, 위쪽 → 아래쪽 방향으로 순서대로 채운 후, 가장 끝 행에 도달할 수 있는 경우 중 최대 합이 되는 경우를 선택하면 답(26)이 됩니다.
3) 조건에 맞게 선택적으로 전진하는 DP
문제 상황에 맞는 적절한 점화식을 세우고, 해당 점화식에 맞춰 DP 테이블에 값을 순서대로 채워넣으면 문제에서 원하는 답을 구할 수 있게 됩니다.
다음과 같이 6개의 숫자 [10, 30, 25, 40, 28, 45]가 주어졌을 때, 가장 긴 증가 부분 수열(LIS)의 길이는?
dp[i]를 마지막으로 고른 원소의 위치가 i인 부분 수열 중 최장 증가 부분 수열의 길이라 정의합니다. 즉, 정확히 i번째 원소를 끝으로 하는 LIS의 길이를 의미합니다.
i번째 원소를 고르기 직전에 골라진 원소의 위치가 j였을 경우를 1부터 i-1까지 전부 가정해보며 점화식을 세울 수 있습니다. dp[j]는 위치 j를 마지막으로 하는 최장 부분 수열의 길이를 들고 있을 것이기 때문에, dp[i]는 dp[j]로부터 답이 갱신되어야 합니다. 단, 직전에 있던 숫자 a[j]가 현재 숫자인 a[i]보다는 작아야 증가 수열이 유지될 것이므로, 해당 경우들 중 최댓값을 구해야합니다.
즉, 아래와 같이 점화식을 세울 수 있습니다.
dp 값을 순서대로 채운 후, 값들 중 최댓값을 선택하면 답(4)이 됩니다.
4) 아이템을 적절히 고르는 DP
문제 상황에 맞는 적절한 점화식을 세우고, 해당 점화식에 맞춰 DP 테이블에 값을 순서대로 채워넣으면 문제에서 원하는 답을 구할 수 있게 됩니다.
가치가 1, 4, 5인 3개의 동전이 주어졌을 때, 금액 8을 거슬러 주기 위해 필요한 최소 동전의 수는?
dp[i]를 지금까지 선택한 동전의 합이 i라 했을 때, 필요한 최소 동전 횟수라고 정의합니다.
합 i를 만는 상황이고 마지막으로 j번째 동전인 coin[j]를 사용했다면, 이전 동전들로 만들었어야 하는 합은 i-coin[j]일 것입니다. 따라서, dp[i]는 dp[i-coin[j]]에 동전 하나를 더 추가했으므로 1을 더한 값과 비교하여 후보들 중 최솟값을 구해야 합니다.(단, i가 coin[j]보다 같거나 커야합니다.)
즉, 아래와 같이 점화식을 세울 수 있습니다. 합을 0 만드는 데 필요한 최소 동전의 수는 아무 동전도 사용하지 않은 경우이므로 0이 됩니다.
dp 값을 순서대로 채운 후, 8에 해당하는 값을 읽으면 답(2)이 됩니다.
도둑이 보석방을 털러 갔습니다. 이때 도둑 가방의 크기가 8이며, 이보다 더 많은 양의 무게에 해당하는 보석들을 담아 나올 수는 없습니다. 이 보석방에 있는 보석의 무게와 가격이 다음과 같고, 보석은 종류별로 단 하나씩만 있을 때, 훔친 보석들의 가격의 최대 합은?
dp[i][j]를 i번째 보석까지 고려했고, 지금까지 선택한 보석 무게의 합이 최대 j였을 때, 가능한 보석 가치의 최대 합이라고 정의합니다.
i번째 보석을 고려하는 경우를 생각해보면, i번째 보석을 가방에 넣는 경우 / 넣지 않는 경우로 나누어 생각할 수 있습니다. 이 두 경우 중 더 큰 가치를 얻을 수 있는 쪽을 선택하면 됩니다.
i번째 보석을 가방에 넣은 경우라면, i-1번째까지 골라진 보석 무게의 합은 j-weight[i]가 될 것입니다. 이 경우라면 이전에 선택한 보석들로부터 얻을 수 있는 최대 가치인 dp[i-1][j-weight[i]]에 현재 i번째 보석을 가방에 넣음으로써 새로 얻게된 가치인 value[i]를 더하여 dp[i-1][j-weight[i]] + value[i]라는 가치를 얻게 됩니다. (단, j가 weight[i]보다 같거나 커야합니다.)
i번째 보석을 가방에 넣지 않은 경우라면, i-1번째까지 골라진 보석 무게의 합이 j가 되는 경우인 dp[i-1][j]가 됩니다.
즉, 아래와 같이 점화식을 세울 수 있습니다. 가방에 아무 보석도 담지 않으면, 무게가 0이고 가치도 0입니다.
dp 값을 왼쪽 → 오른쪽, 위쪽 → 아래쪽 방향으로 순서대로 채운 후, dp[5][8]에 해당하는 값을 읽으면 답(10)이 됩니다.
숫자를 1, 2, 3, 4의 합으로 바꿉니다. 숫자의 합에서 사용된 숫자를 일렬로 나열합니다. 이런 방식으로 암호를 만든다고 가정하면, 8로는 몇 개의 암호를 만들 수 있을까? 예를 들어, 4를 활용하면 1111, 112, 121, 211, 13, 22, 31, 4 와 같이 8개의 암호를 만들 수 있습니다.
앞에 나온 동전고르기 문제와 비슷한 방식으로 생각해볼 수 있습니다. 숫자의 합 → 동전의 합, 숫자의 종류(1, 2, 3, 4) → 동전의 종류
dp[i]를 합이 i인 숫자들로 이루어진 서로 다른 암호의 경우의 수라고 정의합니다.
암호의 마지막 숫자는 1, 2, 3, 4 중 하나일 것입니다.
마지막에 1을 사용한 경우, 마지막 1 이전까지의 합이 i-1인 암호의 경우의 수와 같으므로 dp[i-1]이 됩니다.
마지막에 2를 사용한 경우, 마지막 2 이전까지의 합이 i-2인 암호의 경우의 수와 같으므로 dp[i-2]가 됩니다.
마지막에 3을 사용한 경우, 마지막 3 이전까지의 합이 i-3인 암호의 경우의 수와 같으므로 dp[i-3]이 됩니다.
마지막에 4를 사용한 경우, 마지막 4 이전까지의 합이 i-4인 암호의 경우의 수와 같으므로 dp[i-4]가 됩니다.
위의 경우들을(dp[i-1], d[i-2], dp[i-3], dp[i-4]) 모두 더해주면 dp[i]를 구할 수 있습니다.
즉, 아래와 같이 점화식을 세울 수 있습니다. 합이 0이 되는 경우는 의미상 1가지라 볼 수 있습니다.
dp 값을 순서대로 채운 후, 8에 해당하는 값을 읽으면 답(108)이 됩니다.
5) 문자열 매칭을 할 때의 DP
문제 상황에 맞는 적절한 점화식을 세우고, 해당 점화식에 맞춰 DP 테이블에 값을 순서대로 채워넣으면 문제에서 원하는 답을 구할 수 있게 됩니다.
LCS는 Longest Common Subsequence의 약자로, 최장 공통 부분 수열을 의미합니다. 부분 수열이란, 순서대로 뽑아서 나올 수 있는 수열을 의미하며, 두 문자열에게 공통으로 부분 수열인 경우를 공통 부분 수열이라 부릅니다. 또한, 그 중 가장 길이가 긴 경우를 최장 공통 부분 수열이라고 부릅니다. 문자열 A가 "ACAYKP", 문자열 B가 "CAPCAK"라고 주어질 때 LCS의 길이는? 예를 들어, ABABA와 BAAB의 LCS는 BAB이므로, LCS의 길이는 3이 됩니다.
dp[i][j]를 문자열 A의 i번째까지와 문자열 B의 j번째까지를 활용하여 만들 수 있는 LCS의 길이라고 정의합니다.
조금 고민해보면 케이스는 크게 문자열 A의 i번째 글자와 문자열 B의 j번째 글자가 다른 경우 / 같은 경우로 나누어 생각할 수 있습니다.
문자열 A의 i번째 글자와 문자열 B의 j번째 글자가 다른 경우, i번째 글자와 j번째 글자를 매칭할 수 없습니다. 따라서 문자열 A에서는 i-1번째까지, B에서는 j번째까지 매칭하여 얻은 최적의 결과인 DP[i-1][j]의 값과, 문자열 A에서는 i번째까지, B에서는 j-1번째까지 매칭하여 얻은 최적의 결과인 DP[i][j-1]의 값 중 더 큰 값이 DP[i][j]가 됩니다.
문자열 A의 i번째 글자와 문자열 B의 j번째 글자가 같은 경우, i번째 글자와 j번째 글자를 매칭하는 것이 항상 좋습니다. 따라서 문자열 A의 i번째 글자와 문자열 B의 j번째 글자를 매칭하고 남은 각각 i-1개, j-1개에 해당하는 최적의 결과인 DP[i-1][j-1] 값에 매칭에 성공하여 얻게 된 숫자 1을 더한 값이 DP[i][j]가 됩니다.
즉, 아래와 같이 점화식을 세울 수 있습니다. 첫 번째 행의 경우에는, 문자열 B에 문자열 A의 첫 번째 문자인 'A'가 나오는 순간부터는 항상 'A'와 매칭이 가능해지므로 LCS값이 1이 됩니다. 또한 첫 번째 열의 경우에도, 문자열 A에 문자열 B의 첫 번째 문자인 'C'가 나오는 순간부터는 항상 'C'와 매칭이 가능해지므로 LCS값이 1이 됩니다.
dp 값을 왼쪽 → 오른쪽, 위쪽 → 아래쪽 방향으로 순서대로 채운 후, 각 문자열의 끝 글자까지를 전부 고려했을 때의 LCS값인 dp[6][6]에 해당하는 값을 읽으면 답(4)이 됩니다.
두 개의 문자열 A, B가 주어졌을 때, 두 문자열의 편집 거리를 구해보려고 합니다. 이때 편집 거리란 문자열 A를 문자열 B로 바꾸기 위해 필요한 최소 연산 횟수를 의미하며, 사용 가능한 연산으로는 하나의 문자를 원하는 위치에 삽입하거나, 특정 문자를 삭제하거나, 특정 문자를 다른 문자로 바꾸는 세 가지 연산이 있습니다. 문자열 A가 "ABBBDAAA", 문자열 B가 "BADABBDBA"라고 주어질 때 편집거리는?
dp[i][j]를 문자열 A의 i번째까지, 문자열 B의 j번째까지를 보았을 때 이 둘 사이의 편집거리라고 정의합니다.
조금 고민해보면 케이스는 크게 문자열 A의 i번째 글자와 문자열 B의 j번째 글자가 다른 경우 / 같은 경우로 나누어 생각할 수 있습니다.
문자열 A의 i번째 글자와 문자열 B의 j번째 글자가 다른 경우, i번째 글자와 j번째 글자를 매칭할 수 없습니다. 매칭이 되지 않았으므로 문자열에 삭제, 삽입 혹은 교환을 해주어야하고, 편집거리가 1 늘어납니다.
문자열 A의 i번째 문자를 삭제한다면, 편집거리는A의 i-1번째까지의 글자와 B의 j번째까지의 편집거리와 같으므로 dp[i][j] = dp[i-1][j]+1이 됩니다.
문자열 A에 B의 j번째 해당 문자를 삽입한다면, 편집거리는 A의 i번째까지의 글자와 B의 j-1번째까지의 편집거리와 같으므로 dp[i][j] = dp[i][j-1] + 1이 됩니다.
문자열 A의 i번째 글자를 B의 j번째 글지로 변경한다면, 편집거리는 A의 i-1번째까지의 글자와 B의 j-1번째 글자까지의 편집거리와 같아지므로 dp[i][j] = dp[i-1][j-1]+1이 됩니다.
위의 경우들(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1) 중 최솟값을 구해주면 dp[i][j]를 구할 수 있습니다.
문자열 A의 i번째 글자와 문자열 B의 j번째 글자가 같은 경우, i번째 글자와 j번째 글자를 매칭하면 편집거리가 늘어날 필요가 없습니다. 따라서 문자열 A의 i번째 글자와 문자열 B의 j번째 글자를 제외하고 남은 각각 i-1개, j-1개를 같게 만드는 데 필요한 편집거리 dp[i-1][j-1] 값이 그대로 dp[i][j] 값이 됩니다.
즉, 아래와 같이 점화식을 세울 수 있습니다. 길이 k와 길이 0인 문자열의 편집거리는 k번 삭제 또는 삽입이 일어나면 되므로 의미그대로 k가 됩니다.
dp 값을 왼쪽 → 오른쪽, 위쪽 → 아래쪽 방향으로 순서대로 채운 후, 각 문자열의 끝 글자까지를 전부 고려했을 때의 편집거리 값인 dp[8][9]에 해당하는 값을 읽으면 답(5)이 됩니다.
5. 그리디(Greedy) 알고리즘
그리디 알고리즘의 정의
현재 상황에서 최선이다 싶은 것을 계속 반복하는 알고리즘입니다.
그리디 알고리즘의 특징
그리디 알고리즘은 비록 많은 문제에 대해 최적의 답을 가져와 주지는 못하지만, 그 방법이 굉장히 간단하기 때문에 최적의 답을 구하기 힘든 복잡한 문제에 대해 실제 답에 근사한 결과를 빠르고 간결하게 구하고 싶을 때 자주 사용되기도 합니다.
그리디 알고리즘의 예시
도둑이 보석방을 털러 갔습니다. 이때 도둑 가방의 크기가 8이며, 이보다 더 많은 양의 무게에 해당하는 보석들을 담아 나올 수는 없습니다. 이 보석방에 있는 보석의 무게와 가격이 다음과 같고, 보석은 종류별로 단 하나씩만 있을 때, 훔친 보석들의 가격의 최대 합은? (단, 보석을 쪼개서 담는 것도 가능합니다.)
위에서 봤던 문제는 보석을 쪼개 담을 수 없고, 담거나 전혀 담지 않거나 하는 선택지 밖에 없기 때문에 0/1 Knapsack 문제(DP로 해결)라 불립니다. 이와는 다르게 이 문제는 쪼개서 담을 수 있으므로 Fractional Knapsack 문제(그리디로 해결)라 불립니다.
이 경우에는 무게 대비 가격(가격/무게)이 높은 보석을 우선적으로 담는 것이 항상 좋습니다. 즉, 3번과 1번 보석을 담으면 무게 4, 가격 7이 되며, 이후 2번 보석을 4/6 만큼만 잘라 담으면 담긴 보석의 무게는 8이 되며, 가격은 10.333이 됩니다. 따라서 해당 예시에서 얻을 수 있는 최대 가치는 10.333입니다.
