동적 계획법: 작은 답을 적어 두고 다시 쓰기
피보나치 수를 식 그대로 재귀(recursion) 호출하면 같은 계산을 수십, 수백 번 되풀이합니다. 한 번 구한 답을 적어 두면 하나씩 한 번만 구하면 됩니다. 재귀 트리(recursion tree)에서 되풀이를 세어 보고, 배낭 문제의 표를 한 칸씩 채워 보세요.
한 줄 답. 동적 계획법은 큰 문제를 작은 문제로 나누고, 작은 문제의 답을 한 번만 구해 적어 둔 뒤 다시 쓰는 방법입니다. 두 조건이 맞을 때 씁니다. 같은 작은 문제가 되풀이되고(중복 부분 문제, overlapping subproblems), 작은 문제의 가장 좋은 답으로 큰 문제의 가장 좋은 답을 만들 수 있을 때(최적 부분 구조, optimal substructure)입니다. 쓰는 법은 둘, 메모이제이션(memoization)과 타뷸레이션(tabulation)입니다. 위에서 재귀 호출하며 답을 적어 두거나, 아래에서부터 표를 채웁니다.
막대로 n 을 바꿔 보세요. 원 하나가 함수를 한 번 부른 것이고, 원 안의 숫자 k 는 fib(k) 를 불렀다는 뜻입니다. 같은 k 는 같은 색입니다. 자리가 좁으면 숫자 없이 색만 남깁니다. 트리 아래 줄은 k 마다 부른 횟수입니다. 메모이제이션으로 바꾸면: 굵은 고리와 「이미 풂」이 붙은 원은 적어 둔 답을 꺼내 오는 부름이고, 화살표는 그 답을 처음 계산한 원에서 옵니다. 흐린 원은 메모이제이션이면 아예 부르지 않는 부름입니다. 흐리지 않은 원을 세면 메모이제이션의 부른 횟수가 됩니다.
해 볼 것. ① 처음(n = 6)에는 그냥 재귀가 25번, 메모이제이션이 11번 부릅니다. 트리에서 fib(4) 가 2번, fib(3) 이 3번, fib(2) 가 5번 나옵니다. ② n = 3 이면 둘 다 5번입니다. 되풀이가 거의 없으면 적어 둬도 얻는 것이 없습니다. ③ n = 10 이면 177번과 19번입니다. fib(1) 하나만 55번 불립니다. ④ n = 12 까지 올리면 465번과 23번입니다. n 이 하나 늘 때마다 그냥 재귀는 약 1.62배(177 → 287 → 465)가 되고, 메모이제이션은 2번씩 늘어납니다.
1. 동적 계획법이란: 두 조건
피보나치 수는 앞의 두 수를 더해 만듭니다: 0, 1, 1, 2, 3, 5, 8, 13, … 식으로는 이렇습니다.
fib(n) = fib(n − 1) + fib(n − 2) (n ≥ 2)
fib(0) = 0, fib(1) = 1
n: 몇 번째 수인지. 0 부터 셉니다.fib(n): n 번째 피보나치 수. 구하려는 큰 문제입니다.fib(n − 1),fib(n − 2): 바로 앞의 두 수. 큰 문제를 푸는 데 필요한 작은 문제입니다.fib(0) = 0,fib(1) = 1: 더 나눌 수 없는 가장 작은 문제의 답. 재귀가 여기서 멈춥니다.
이 식대로 짠 함수는 fib(6) 을 구하려고 fib(4) 를 2번, fib(2) 를 5번 다시 구합니다. 같은 답을 매번 처음부터 다시 계산하는 것입니다. 동적 계획법은 이 낭비를 없앱니다. 다음 두 조건이 맞는 문제에 씁니다.
- 중복 부분 문제: 같은 작은 문제가 되풀이된다. fib(6) 안에서 fib(4) 가 두 번 필요합니다. 되풀이가 없으면 적어 둬도 다시 꺼낼 일이 없습니다. 병합 정렬처럼 나눈 반쪽들이 겹치지 않는 문제는 분할 정복(divide and conquer)으로 그냥 나눠서 풉니다(병합 정렬과 퀵 정렬).
- 최적 부분 구조: 작은 문제의 가장 좋은 답으로 큰 문제의 가장 좋은 답을 만든다. 아래 배낭 문제에서, 한도 8 의 가장 좋은 답에 C(무게 4)가 들어 있다면, 나머지는 「C 앞의 물건들로 한도 4 를 가장 좋게 채운 답」이어야 합니다. 나머지를 더 좋게 채우는 길이 있다면 그것으로 바꿔 끼워 전체가 더 좋아질 테니까요.
2. 두 가지 쓰는 법
메모이제이션: 위에서 재귀 호출하며 적어 두기. 식 그대로 재귀 호출하되, 답을 구하면 적어 두고, 부를 때마다 먼저 적어 둔 것이 있는지 봅니다. 있으면 계산하지 않고 꺼냅니다. 필요한 작은 문제만 풉니다. 실험의 「메모이제이션」이 이것입니다. Python 에서는 표준 라이브러리 functools.cache 를 함수 위에 한 줄 붙이면 됩니다.
from functools import cache
@cache
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib(10)) # 55
print(fib.cache_info()) # CacheInfo(hits=8, misses=11, maxsize=None, currsize=11)
cache_info() 의 misses 11 은 새로 계산한 수(fib(0) ~ fib(10)), hits 8 은 적어 둔 답을 꺼낸 수입니다. 합 19 가 실험에서 n = 10 일 때 「메모이제이션」의 부른 횟수와 같습니다. 문서에 따르면 cache 는 크기 제한이 없는 함수 캐시이고, 인자를 사전(dict)의 키로 써서 답을 찾습니다. 그래서 인자는 해시할 수 있는 값이어야 하고(해시 표), 같은 인자에 늘 같은 답을 내는 함수에만 붙여야 합니다.
타뷸레이션: 아래에서 표 채우기. 가장 작은 문제부터 차례로 답을 표에 채웁니다. fib(0), fib(1), fib(2), … 순서로 채우면 각 칸을 채울 때 필요한 앞 칸이 이미 있습니다. 재귀 호출하지 않고 반복문 하나로 끝납니다. 채우는 순서는 직접 정해야 하고, 필요 없는 칸까지 다 채웁니다. 아래 배낭 실험이 이 방식입니다.
3. 배낭 문제: 표를 한 칸씩 채우기
무게 한도가 있는 배낭에 물건을 담습니다. 물건마다 무게와 값이 있고, 하나씩만 있으며 쪼갤 수 없습니다(넣거나 안 넣거나). 한도를 넘지 않으면서 값의 합을 가장 크게 하려면 무엇을 넣어야 할까요? 이 쪽의 물건은 지어낸 넷입니다: A 무게 5 값 11, B 무게 4 값 8, C 무게 4 값 7, D 무게 2 값 3. 한도는 8 입니다.
표의 줄은 「물건을 어디까지 볼지」, 칸은 「한도」입니다. 칸 하나를 채우는 식이 점화식입니다.
best[0][c] = 0, best[i][0] = 0
best[i][c] = best[i − 1][c] (wᵢ > c: 들어가지 않을 때)
best[i][c] = max(best[i − 1][c], vᵢ + best[i − 1][c − wᵢ]) (wᵢ ≤ c)
i: 몇 번째 물건까지 보는지. 표의 줄입니다. 0 이면 물건이 없습니다.c: 지금 쓸 수 있는 무게 한도. 표의 칸입니다.best[i][c]: 물건 1 ~ i 만 써서 한도 c 안에서 얻는 가장 큰 값의 합. 칸에 적는 숫자입니다.wᵢ,vᵢ: i 번째 물건의 무게와 값.best[i − 1][c]: i 번째를 안 넣을 때. 한도는 그대로 두고 앞의 물건들로만 채운 값, 곧 바로 위 칸(↓)입니다.vᵢ + best[i − 1][c − wᵢ]: i 번째를 넣을 때. 넣고 남은 한도 c − wᵢ 를 앞의 물건들로 가장 좋게 채운 값에 vᵢ 를 더합니다. 위 줄에서 wᵢ 칸만큼 왼쪽(↘)입니다.max: 둘 중 큰 값. 답은 맨 아래 맨 오른쪽 칸best[n][C]입니다(n 은 물건 수, C 는 한도).
「넣을 때」를 늘 위 줄에서 가져오므로 같은 물건을 두 번 넣지 않습니다.
「다음」을 누르면 한 칸씩 채웁니다. 주황 테두리가 지금 채우는 칸입니다. 파랑 화살표 ↓ 는 안 넣을 때 바로 위 칸에서, 초록 화살표 ↘ 는 넣을 때 위 줄에서 무게만큼 왼쪽 칸에서 값을 가져옵니다. 화살표가 나오는 칸 위에 셈을 적고, 큰 쪽 화살표를 굵게 그립니다. 물건이 무거워 못 넣는 칸은 파랑 화살표 하나뿐입니다. 다 채우면 오른쪽 아래에서부터 주황 화살표를 따라 거꾸로 올라가며 고른 물건에 ✓ 를 붙입니다.
해 볼 것. ① 걸음 6(A까지, 한도 5)에서 처음으로 물건이 들어갑니다: 0 대신 11. 걸음 13(B까지, 한도 4)에서는 B 가 들어가 8 입니다. ② 걸음 25(C까지, 한도 8)에서 안 넣으면 11, 넣으면 7 + 8 = 15 입니다. B 와 C 를 같이 넣는 길이 여기서 나옵니다. ③ 걸음 31(D까지, 한도 6)은 두 값이 11 로 같습니다. ④ 걸음 33 이 마지막 칸이고 답은 15 입니다. 걸음 34 ~ 37 에서 거꾸로 따라가면 D 는 빠지고 C, B 가 골라집니다. 걸음 38 에서 모든 묶음 16가지를 따진 값도 15 이고, 그리디는 14 입니다.
4. 손으로 따라가기
실험과 같은 물건, 같은 한도로 표를 끝까지 채운 모습입니다. 줄마다 왼쪽에서 오른쪽으로, 위 줄만 보고 채웁니다.
| 줄 \ 한도 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 없음 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A까지 (5, 11) | 0 | 0 | 0 | 0 | 0 | 11 | 11 | 11 | 11 |
| B까지 (4, 8) | 0 | 0 | 0 | 0 | 8 | 11 | 11 | 11 | 11 |
| C까지 (4, 7) | 0 | 0 | 0 | 0 | 8 | 11 | 11 | 11 | 15 |
| D까지 (2, 3) | 0 | 0 | 3 | 3 | 8 | 11 | 11 | 14 | 15 |
- A 줄. A 의 무게가 5 라 한도 0 ~ 4 에는 들어가지 않아 위 칸 0 을 그대로 씁니다. 한도 5 부터는
max(0, 11 + 0) = 11. - B 줄, 한도 8. 안 넣으면 위 칸 11. 넣으면
8 + best[A][8 − 4] = 8 + 0 = 8. A 와 B 는 합쳐 무게 9 라 같이 못 넣습니다. 큰 쪽을 적어 11. - C 줄, 한도 8. 안 넣으면 11. 넣으면
7 + best[B][4] = 7 + 8 = 15. 큰 쪽을 적어 15. - D 줄, 한도 7. 안 넣으면 11. 넣으면
3 + best[C][5] = 3 + 11 = 14. 큰 쪽을 적어 14(A 와 D). - D 줄, 한도 8. 안 넣으면 15. 넣으면
3 + best[C][6] = 3 + 11 = 14. 큰 쪽을 적어 15. 이것이 답입니다. - 역추적(traceback): 거꾸로 따라가기. D 줄 한도 8 의 15 는 위 칸 15 와 같으니 D 없이 나옵니다. C 줄의 15 는 위 칸 11 과 다르니 C 를 넣었습니다. 한도를 8 − 4 = 4 로 옮기면 B 줄의 8 은 위 칸 0 과 다르니 B 를 넣었습니다. 한도가 4 − 4 = 0 이 되고, A 줄의 0 은 위 칸과 같아 A 는 빠집니다. 고른 물건은 B, C, 무게 8, 값 15.
Python 으로 옮기면 이렇습니다(15줄).
def knapsack(items, limit):
"""items: [(이름, 무게, 값), ...]. 한도 안에서 가장 큰 값의 합과 고른 물건."""
best = [[0] * (limit + 1)] # 물건 0개: 모두 0
for _, weight, value in items:
above = best[-1]
best.append([max(above[c], value + above[c - weight]) if weight <= c else above[c]
for c in range(limit + 1)])
picked, c = [], limit
for i in range(len(items), 0, -1): # 역추적
if best[i][c] != best[i - 1][c]:
picked.append(items[i - 1][0])
c -= items[i - 1][1]
return best[-1][limit], picked[::-1]
print(knapsack([("A", 5, 11), ("B", 4, 8), ("C", 4, 7), ("D", 2, 3)], 8)) # (15, ['B', 'C'])
5. 그리디가 틀리는 예
그리디는 지금 가장 좋아 보이는 것을 고르고 되돌리지 않습니다. 배낭에서 흔히 떠올리는 그리디는 「무게 1 당 값(값÷무게)이 큰 것부터 넣기」입니다. 실험의 물건은 값÷무게가 A 2.2, B 2, C 1.75, D 1.5 입니다.
- 그리디: A 를 넣습니다(남은 한도 3). B 와 C 는 무게 4 라 들어가지 않습니다. D 를 넣습니다(남은 한도 1). A, D 로 값 14.
- 동적 계획법: B, C 로 값 15. 모든 묶음 16가지를 다 따져도 15 가 가장 큽니다.
A 가 무게당 값은 가장 좋지만, A 를 먼저 넣으면 남은 한도 3 이 거의 쓸모없어집니다. 그리디는 이 뒤의 일을 보지 않습니다. 동적 계획법은 칸마다 「넣을 때」와 「안 넣을 때」를 둘 다 따지고 둘 다 표에 남겨 두므로, 한 번의 선택이 나중을 망치는지 알 수 있습니다.
6. 걸리는 시간
동적 계획법의 시간은 칸 수 × 칸마다 하는 일입니다. 칸 하나는 한 번만 채우기 때문입니다(시간 복잡도).
- 피보나치, 메모이제이션. 칸은 fib(0) ~ fib(n) 의 n + 1 개, 칸마다 더하기 한 번. n 이 두 배면 시간도 두 배(O(n)). 실험의 부른 횟수는 2n − 1 입니다.
- 피보나치, 그냥 재귀. n 이 하나 늘 때마다 부른 횟수가 약 1.62배(177 → 287 → 465). 지수로 늘어납니다. 같은 칸을 몇 번이고 다시 채우는 셈입니다.
- 배낭. 칸은 (n + 1) × (C + 1) 개, 칸마다 두 값 비교 한 번. 시간은 O(n·C). 실험에서 실제로 계산한 칸은 물건 4 × 한도 8 = 32 개입니다. 모든 묶음을 따지면 2ⁿ 가지라 물건이 하나 늘 때마다 두 배가 됩니다.
배낭의 C 는 물건의 수가 아니라 한도라는 숫자의 크기입니다. 한도가 두 배면 표도 두 배입니다. 한도를 원 단위 예산처럼 아주 큰 수로 적으면 표가 감당할 수 없이 커집니다. 이때는 단위를 줄이거나(만 원 단위로) 다른 방법을 봅니다. 메모리는 표 전체가 (n + 1) × (C + 1) 칸입니다. 답의 값만 필요하면 바로 위 줄만 남겨 C + 1 칸으로 줄일 수 있습니다. 위의 코드처럼 거꾸로 따라가려면 표 전체를 남겨야 합니다.
7. 언제 무엇을 쓰나: 그리디, 동적 계획법, 백트래킹
셋 다 「여러 선택 가운데 가장 좋은 것」을 찾는 방법입니다. 배낭(물건 n 개, 한도 C)을 예로 비교합니다.
| 그리디 | 동적 계획법 | 백트래킹 | |
|---|---|---|---|
| 하는 일 | 지금 가장 좋아 보이는 것을 고르고 되돌리지 않는다 | 작은 문제의 답을 표에 적어 두고 다시 쓴다 | 하나씩 넣어 보고, 안 되면 되돌아가 다른 길을 넣어 본다 |
| 답 | 틀릴 수 있다(이 쪽: 14) | 늘 맞다(15) | 늘 맞다(15) |
| 걸리는 시간 | 가장 좋을 때·보통·가장 나쁠 때 모두 O(n log n). 값÷무게로 정렬하는 데 드는 시간 | 가장 좋을 때·보통·가장 나쁠 때 모두 O(n·C). 표의 칸 수 | 가장 좋을 때는 가지치기로 일찍 끝난다. 보통은 입력과 가지치기에 따라 다르다. 가장 나쁠 때 O(2ⁿ): 물건 하나 늘면 두 배 |
| 더 드는 메모리 | O(n): 정렬한 순서 | O(n·C): 표. 값만이면 O(C) | O(n): 지금까지 고른 것 |
| 좋은 점 | 빠르고 짧다 | 정확하고, 시간이 입력의 모양에 흔들리지 않는다 | 조건이 복잡해도 쓸 수 있다. 가능한 답을 모두 내야 할 때도 쓴다 |
| 나쁜 점 | 맞다는 것을 보일 수 있는 문제에만 쓸 수 있다 | 작은 문제를 무엇으로 잡을지 정해야 한다. 한도 같은 숫자가 크면 표가 커진다 | 가장 나쁠 때 아주 느리다 |
| 쓰는 경우 | 쪼갤 수 있는 배낭, 최소 신장 트리, 다익스트라 | 작은 문제가 되풀이되고 그 가짓수(칸 수)가 감당할 만할 때 | n 이 작거나, 가지치기가 잘 듣거나, 모든 경우를 나열해야 할 때 |
어디에 쓰나
- 두 글의 차이. 한 글을 다른 글로 바꾸는 데 드는 가장 적은 고치기 수(편집 거리)와 두 글에 같은 차례로 들어 있는 가장 긴 부분(가장 긴 공통 부분 수열)을 타뷸레이션으로 구합니다. 맞춤법 제안, 파일 비교(diff)가 푸는 문제입니다.
- 예산 안에서 고르기. 한도 안에서 값의 합을 가장 크게 하는 일은 모두 배낭 문제의 모양입니다.
- 거스름돈을 가장 적은 동전으로. 동전의 묶음에 따라 큰 동전부터 내는 그리디가 틀릴 수 있어, 금액 0 부터 표를 채웁니다.
- 격자 위의 길. 길의 수 세기, 가장 싼 길 찾기처럼 「이 칸까지의 답 = 앞 칸들의 답으로 만든 것」인 문제.
- 함수 캐시. 같은 인자에 같은 답을 내는 비싼 함수에
@cache를 붙이는 것도 같은 생각입니다.
자주 묻는 것
메모이제이션과 타뷸레이션 가운데 무엇을 쓰나요?
점화식을 그대로 옮기고 싶으면 메모이제이션이 쉽습니다. Python 이면 @cache 한 줄로 끝나고, 필요한 작은 문제만 풉니다. 재귀가 아주 깊어질 것 같거나 메모리를 줄여야 하면 타뷸레이션을 씁니다. 재귀가 없고, 바로 앞 줄만 남기는 식으로 메모리를 줄이기 쉽습니다.
동적 계획법이면 늘 빠른가요?
아닙니다. 걸리는 시간은 칸 수 × 칸마다 하는 일입니다. 칸이 너무 많으면 느립니다. 배낭은 칸 수가 한도라는 숫자에 비례해서, 한도가 아주 큰 수면 표가 감당할 수 없이 커집니다. 작은 문제가 되풀이되지 않는 문제라면 적어 둬도 다시 꺼낼 일이 없어 얻는 것이 없습니다.
그리디로 풀어도 되는지 어떻게 아나요?
지금 가장 좋아 보이는 것을 고르는 것이 늘 가장 좋은 답의 일부라는 것을 보일 수 있을 때만 됩니다. 물건을 쪼개 담을 수 있는 배낭이면 값÷무게가 큰 것부터 담는 그리디가 맞습니다. 쪼갤 수 없으면 이 쪽의 예처럼 틀릴 수 있어 동적 계획법을 씁니다.
낱말
| 여기서 쓴 말 | 책에서 부르는 말 |
|---|---|
| 작은 답을 적어 두고 다시 쓰기 | 동적 계획법(dynamic programming, DP) |
| 위에서 재귀 호출하며 적어 두기 | 메모이제이션(memoization), 하향식(top-down) |
| 아래에서 표 채우기 | 타뷸레이션(tabulation), 상향식(bottom-up) |
| 같은 작은 문제가 되풀이된다 | 중복 부분 문제(overlapping subproblems) |
| 작은 문제의 가장 좋은 답으로 큰 문제의 가장 좋은 답을 만든다 | 최적 부분 구조(optimal substructure) |
| 칸 하나를 앞 칸들로 적는 식 | 점화식(recurrence relation) |
| 표의 칸 하나, 작은 문제 하나 | 상태(state) |
| 함수가 자기를 다시 부르기, 그 부름을 그린 그림 | 재귀(recursion), 재귀 트리(recursion tree) |
| 쪼갤 수 없는 배낭 문제 | 0-1 배낭 문제(0-1 knapsack problem) |
| 쪼갤 수 있는 배낭 문제 | 분할 가능 배낭 문제(fractional knapsack problem) |
| 거꾸로 따라가 고른 것 찾기 | 해 복원(reconstruction), 역추적(traceback) |
| 숫자의 크기(한도)에 비례하는 시간 | 의사 다항 시간(pseudo-polynomial time) |
| 나눈 문제가 겹치지 않을 때 나눠 풀기 | 분할 정복(divide and conquer) |
출처
- Python 문서, functools:
cache(크기 제한 없는 함수 캐시, 인자는 해시할 수 있어야 함),cache_info().