동적 계획법(DP): 같은 문제를 두 번 풀지 않는 기술
서론
동적 계획법(Dynamic Programming, DP)은 이름이 문제입니다. “동적”도 “계획법”도 실제 내용과 별 상관이 없습니다. 1950년대 리처드 벨만이 연구비를 따내려고 멋있어 보이는 이름을 붙인 것이라는 일화가 유명할 정도입니다.
이름을 걷어내면 DP의 핵심은 한 문장입니다.
큰 문제를 작은 문제로 쪼개되, 한 번 푼 작은 문제의 답은 저장해 두고 재사용한다.
이게 전부입니다. 어렵게 느껴지는 이유는 알고리즘이 복잡해서가 아니라, “어떻게 쪼갤지”(점화식 설계)가 문제마다 다르기 때문입니다. 이 글에서는 DP가 성립하는 조건부터 시작해, 피보나치 → 배낭 → LCS 순으로 점화식을 직접 세워봅니다.
1. DP가 통하는 두 가지 조건
아무 문제나 DP로 풀리지는 않습니다. 다음 두 조건이 동시에 성립해야 합니다.
① 최적 부분구조 (Optimal Substructure) 큰 문제의 최적해가 작은 부분문제의 최적해로 구성됩니다. “최단 경로의 일부 구간도 그 구간의 최단 경로다” 같은 성질입니다. 이게 있어야 작은 답을 모아 큰 답을 만들 수 있습니다.
② 겹치는 부분문제 (Overlapping Subproblems) 문제를 쪼개다 보면 같은 부분문제가 반복해서 등장합니다. 이게 있어야 “저장해 두고 재사용”이 의미를 가집니다.
두 조건은 역할이 다릅니다. ①이 없으면 애초에 쪼개서 합칠 수가 없고(→ DP 불가), ②가 없으면 쪼개도 재사용할 게 없습니다(→ 그냥 분할정복이면 충분).
분할정복(merge sort 등)은 ①은 있지만 ②가 없습니다. 부분문제가 겹치지 않으니 저장해도 이득이 없죠. DP는 ②가 있는 분할정복이라고 봐도 됩니다.
2. 피보나치로 보는 핵심
피보나치 수열 $F(n) = F(n-1) + F(n-2)$, $F(0)=0,\ F(1)=1$. 정의를 그대로 재귀로 옮기면:
1
2
3
4
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
깔끔하지만 치명적으로 느립니다. fib(5)를 호출하면 무슨 일이 벌어지는지 보면 답이 나옵니다.
왼쪽: n이 커질수록 순수 재귀의 호출 횟수가 지수로 폭발한다(세로축 로그). 오른쪽: fib(5) 재귀 트리. 같은 색 노드는 똑같은 부분문제를 처음부터 다시 계산하고 있다.
오른쪽 트리에서 fib(3)은 2번, fib(2)는 3번 계산됩니다. n이 커지면 이 중복이 눈덩이처럼 불어나 전체 호출이 $O(2^n)$이 됩니다. 바로 겹치는 부분문제가 낭비되고 있는 현장입니다.
처방 1 — 메모이제이션 (Top-down)
“한 번 푼 건 저장한다”를 그대로 코드로 옮깁니다. 재귀는 그대로 두되, 답을 캐시에 적어두고 다음엔 꺼내 씁니다.
1
2
3
4
5
6
7
def fib(n, memo={}):
if n < 2:
return n
if n in memo: # 이미 풀었으면 꺼내 쓴다
return memo[n]
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
각 부분문제 fib(k)는 딱 한 번만 실제로 계산됩니다. 호출 수가 $O(2^n) \to O(n)$으로 떨어집니다(위 그림 왼쪽 파란 선).
처방 2 — 타뷸레이션 (Bottom-up)
재귀를 아예 걷어내고, 작은 것부터 표를 채워 올라갑니다.
1
2
3
4
5
6
7
8
def fib(n):
if n < 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] # 작은 답으로 큰 답을 만든다
return dp[n]
같은 $O(n)$이지만 재귀 호출 스택이 없어 더 빠르고 안전합니다. 피보나치는 직전 두 값만 필요하므로 배열 대신 변수 2개로 $O(1)$ 공간까지 줄일 수 있습니다.
3. Top-down vs Bottom-up
두 방식은 같은 점화식을 푸는 두 방향입니다.
| Top-down (메모이제이션) | Bottom-up (타뷸레이션) | |
|---|---|---|
| 방향 | 큰 문제 → 작은 문제 (재귀) | 작은 문제 → 큰 문제 (반복) |
| 작성 | 재귀에 캐시만 추가 — 직관적 | 채우는 순서를 직접 설계 |
| 계산 범위 | 필요한 부분문제만 계산 | 표 전체를 계산 |
| 오버헤드 | 재귀 호출·스택 | 없음 (보통 더 빠름) |
| 위험 | 깊으면 스택 오버플로 | 없음 |
실무 감각: 점화식을 떠올릴 땐 Top-down으로 먼저 쓰고(자연스럽다), 성능이나 스택이 걸리면 Bottom-up으로 옮긴다. 부분문제 공간이 듬성듬성해서 일부만 필요하면 Top-down이 오히려 유리하다.
4. 점화식 설계하는 법 — DP의 진짜 난관
DP에서 어려운 건 구현이 아니라 점화식 세 가지를 정의하는 것입니다.
- 상태(state): 부분문제를 무엇으로 식별하는가. →
dp[...]의 인덱스가 곧 상태다. - 전이(transition): 작은 상태들로 현재 상태를 어떻게 만드는가. → 점화식 본체.
- 기저(base case): 더 쪼갤 수 없는 가장 작은 답.
피보나치라면 — 상태: dp[i](i번째 값), 전이: dp[i]=dp[i-1]+dp[i-2], 기저: dp[0]=0, dp[1]=1. 이 틀을 배낭과 LCS에도 똑같이 적용해봅니다.
5. 예제 ① — 0/1 배낭 문제
용량이 $W$인 가방에, 무게 $w_i$·가치 $v_i$인 물건 $n$개 중 일부를 담아 가치 합을 최대화합니다. 각 물건은 담거나(1) 말거나(0).
상태 정의. dp[i][w] = 물건 1..i 까지만 고려하고 용량이 $w$일 때의 최대 가치.
전이. $i$번째 물건 앞에서 선택지는 둘뿐입니다.
\[dp[i][w] = \max\!\begin{cases} dp[i-1][w] & \text{(물건 } i \text{ 안 담음)}\\[4pt] dp[i-1][\,w - w_i\,] + v_i & \text{(담음, } w_i \le w \text{일 때)} \end{cases}\]기저. dp[0][w] = 0 (물건이 없으면 가치 0).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def knapsack(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
dp[i][w] = dp[i - 1][w] # 안 담음
if weights[i - 1] <= w: # 담을 수 있으면
cand = dp[i - 1][w - weights[i - 1]] + values[i - 1]
dp[i][w] = max(dp[i][w], cand) # 더 나은 쪽
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack(weights, values, 8)) # -> 10 (물건 #2+#4: 무게 3+5=8, 가치 4+6=10)
표를 한 칸씩 채워 올라가는 모습은 이렇습니다.
각 칸 dp[i][w]는 바로 위 칸(안 담음)과 왼쪽 위 어딘가(담음)만 보고 채워진다. 답은 우하단(빨간 원, =10).
각 칸이 위 행의 값 두 개만 참고한다는 점에 주목하세요. 이게 최적 부분구조입니다. 전체 시간 복잡도는 $O(nW)$ — 표 칸 수만큼입니다.
참고: $O(nW)$는 $W$가 입력 “값”에 비례하므로 진짜 다항식이 아니라 유사 다항(pseudo-polynomial)입니다. 그래서 0/1 배낭은 NP-hard지만 $W$가 작으면 DP로 빠르게 풀립니다.
6. 예제 ② — 최장 공통 부분수열 (LCS)
두 문자열 "ABCBDAB", "BDCAB"에서 순서를 지키되 연속일 필요는 없는 가장 긴 공통 수열을 찾습니다(여기선 "BCAB", 길이 4). diff·DNA 정렬·맞춤법 검사의 뼈대입니다.
상태. dp[i][j] = $X$의 앞 $i$글자와 $Y$의 앞 $j$글자의 LCS 길이.
전이. 두 문자열의 끝 글자를 비교합니다.
\[dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & x_i = y_j \;\text{(짝이 맞으면 길이 +1)}\\[4pt] \max\bigl(dp[i-1][j],\ dp[i][j-1]\bigr) & x_i \ne y_j \;\text{(한쪽을 버린다)} \end{cases}\]기저. 한쪽이 빈 문자열이면 LCS는 0 → dp[0][j]=dp[i][0]=0.
1
2
3
4
5
6
7
8
9
10
11
12
def lcs(X, Y):
m, n = len(X), len(Y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
print(lcs("ABCBDAB", "BDCAB")) # -> 4
배낭과 점화식 모양이 다르지만 틀은 똑같습니다. 2차원 상태, 위·왼쪽·대각선 칸으로부터의 전이, 0으로 시작하는 기저. 복잡도 $O(mn)$.
7. DP는 어디에 다른 얼굴로 숨어 있나
알고리즘 문제집 밖에서도 DP는 기계학습·통계의 핵심 엔진으로 돌아갑니다. 이름만 다를 뿐 전부 “부분문제 답을 표에 채우는” 같은 골격입니다.
- 편집 거리(Edit Distance): LCS의 사촌. 오타 교정·DNA 정렬·
diff가 전부 같은 2차원 DP. - 비터비 알고리즘(Viterbi): HMM에서 가장 그럴듯한 은닉 상태열을 찾는 것 = 격자 위 최장(최대확률) 경로 DP. 음성 인식·품사 태깅의 표준.
- DTW(Dynamic Time Warping): 길이가 다른 두 시계열을 정렬하는 거리. 역시 2차원 누적 비용 표를 채운다.
- CRF의 forward-backward: 시퀀스 라벨링의 우도 계산이 DP.
- 강화학습의 가치 반복(Value Iteration): 벨만 방정식 $V(s)=\max_a \big[r + \gamma\sum_{s’} P\,V(s’)\big]$ 자체가 상태에 대한 DP 점화식이다.
마지막 항목 — 벨만 방정식이 바로 DP의 원형이고, 강화학습은 이 글의 점화식 사고를 “상태·행동·보상”으로 확장한 것입니다. 그건 다음 글에서 따로 다루겠습니다.
마치며
DP는 새로운 알고리즘이 아니라 사고법입니다. 정리하면:
- 조건 확인 — 최적 부분구조(쪼개서 합치기) + 겹치는 부분문제(재사용할 게 있나).
- 점화식 설계 — 상태 / 전이 / 기저, 이 세 가지만 정의하면 끝.
- 방향 선택 — 직관적인 Top-down(메모이제이션)으로 쓰고, 필요하면 Bottom-up(타뷸레이션)으로 최적화.
피보나치든 배낭이든 비터비든, 결국 같은 질문 하나로 환원됩니다.
“이 문제를, 이미 풀어둔 더 작은 문제들의 답으로 어떻게 표현할 수 있는가?”
이 한 문장을 점화식으로 옮길 수 있으면 — 그게 DP를 푼 것입니다.