큰 문제를 작은 문제로 쪼갰는데 같은 작은 문제가 자꾸 다시 나오면, 한 번 푼 답을 표에 적어 두고 꺼내 쓴다. 피보나치 수를 그대로 재귀로 구하면 같은 값을 수백만 번 다시 구하지만, 표에 적으면 값마다 한 번씩만 구한다. 대신 “작은 문제의 가장 좋은 답을 이어 붙이면 큰 문제의 가장 좋은 답이 된다”는 성질이 있어야 하고, 표의 칸(상태)을 잘못 정하면 답이 틀리거나 표가 너무 커진다.
예시로 보기
같은 계산의 반복
피보나치 수 f(n) = f(n − 1) + f(n − 2)를 그대로 재귀로 구하면 f(30)을 구하는 데 함수를 2,692,537번 부른다. f(28)은 f(30)에서도, f(29)에서도 구하는 식으로 같은 값을 계속 다시 구하기 때문이다. 한 번 구한 값을 딕셔너리에 적어 두면 함수를 59번 부르고, 실제 계산은 f(0) ~ f(30)의 31번뿐이다.
flowchart TD
a["f(4)"] --> b["f(3)"]
a --> c["f(2)"]
b --> d["f(2)"]
b --> e["f(1)"]
d --> f["f(1)"]
d --> g["f(0)"]
c --> h["f(1)"]
c --> i["f(0)"]
f(4)를 그대로 재귀로 구할 때의 호출 나무다. f(2) 아래 나무가 통째로 두 번 나온다. n이 커지면 이런 겹침이 층마다 쌓여 호출 수가 불어난다1.
세로축은 10배마다 한 칸이다. 그대로 재귀로 구하면 n이 1 늘 때마다 부르는 횟수가 약 1.6배씩 늘어 곧은 선으로 올라간다. 표에 적어 두면 2n − 1번이라 n = 30에서도 59번이다2.
그리디가 틀린 동전 문제
1원, 3원, 4원 동전으로 6원을 가장 적은 개수로 낸다. 그리디는 4 + 1 + 1로 3개를 냈지만 답은 3 + 3의 2개다. dp[x]를 “x원을 내는 최소 개수”로 두고 작은 금액부터 채운다. x원의 마지막 동전이 c원이면 나머지는 x − c원이니, dp[x] = (가능한 c마다 dp[x − c] + 1 중 최솟값)이다.
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| dp[x] | 0 | 1 | 2 | 1 | 1 | 2 | 2 |
| 마지막 동전 | 1 | 1 | 3 | 4 | 1 또는 4 | 3 |
dp[6] = min(dp[5] + 1, dp[3] + 1, dp[2] + 1) = min(3, 2, 3) = 2다. 모든 마지막 동전을 다 따져 보니 그리디처럼 한 가지만 믿다가 틀리는 일이 없다.
네 가지를 정한다
DP 문제는 늘 다음 네 가지를 정하면 풀린다. 동전 문제로 보인다.
| 정할 것 | 동전 문제 | 흔한 실수 |
|---|---|---|
| 상태: 표의 한 칸이 뜻하는 것 | dp[x] = x원을 내는 최소 동전 수 | 뜻을 말로 못 적는다. 답을 정하는 데 필요한 정보를 빠뜨린다 |
| 점화식: 칸을 더 작은 칸으로 구하는 식 | dp[x] = min(dp[x − c] + 1) | “마지막 선택”을 모두 따지지 않는다 |
| 시작값: 더 쪼갤 수 없는 칸 | dp[0] = 0, 나머지는 무한대 | 0과 무한대를 헷갈린다 |
| 계산 순서: 필요한 칸이 먼저 채워지는 순서 | x = 1, 2, …, 목표 | 아직 안 채운 칸을 읽는다 |
두 방식이 있다. 위에서부터는 재귀로 풀면서 구한 답을 기억해 둔다(메모이제이션). 아래에서부터는 작은 칸부터 표를 채운다(타뷸레이션). 결과는 같다. 위에서부터는 필요한 칸만 계산하고 점화식을 그대로 옮기기 쉽다. 아래에서부터는 재귀 한도 걱정이 없고 대개 더 빠르다. 파이썬에서 재귀 깊이가 수천이 되면 기본 한도(1,000)에 걸린다.
정의
- 최적 부분 구조(optimal substructure): 큰 문제의 가장 좋은 답 안에 들어 있는 작은 문제의 답도 그 작은 문제의 가장 좋은 답이다.
- 겹치는 부분 문제(overlapping subproblems): 쪼개 나가면 같은 작은 문제가 여러 번 나온다.
동전 문제의 점화식: 동전 집합 \(C \subseteq \mathbb{Z}^{+}\)와 \(x \in \mathbb{N}\)(\(\in\)은 “~에 속한다”)에 대해
\[dp[0] = 0, \qquad dp[x] = \min_{c \in C,\ c \le x} \big(dp[x - c] + 1\big) \quad (x \ge 1).\]쓸 수 있는 \(c\)가 없으면 \(dp[x] = \infty\)다.
증명
동전 점화식이 맞다는 것을 x에 대한 강한 귀납법으로 보인다. 핵심은 “가장 좋은 답에서 마지막 동전을 떼어 낸 나머지도 가장 좋은 답”이라는 잘라 붙이기(cut-and-paste) 논증이다3.
증명 펼치기
x보다 작은 모든 금액에서 dp가 정확하다고 하자(강한 귀납 가정). x ≥ 1원을 내는 방법이 있다고 하자.
- 점화식 값은 어떤 방법의 개수다: 각 c에 대해 dp[x − c] + 1은 “x − c원을 가장 적게 낸 뒤 c를 하나 더한” 방법의 개수다. 그래서 최솟값 dp[x]는 실제로 가능한 개수이고, 최소 개수 이상이다.
- 최소 개수는 점화식 값 이상이다: x원을 가장 적게(k개) 내는 방법을 하나 잡고, 그 마지막 동전을 c라 하자. 나머지 k − 1개는 x − c원을 낸다.
- 잘라 붙이기: 나머지 k − 1개가 x − c원의 최소가 아니라면, x − c원을 더 적게 내는 방법에 c를 붙여 x원을 k개보다 적게 낼 수 있다. 이것은 k가 최소라는 데 모순이다. 그래서 k − 1 = dp[x − c]다(귀납 가정).
- 결론: k = dp[x − c] + 1 ≥ dp[x]다. 1과 합치면 dp[x] = k다. ∎
스스로 설명해 보기
1. 3단계의 “더 적게 내는 방법에 c를 붙인다”가 가능한 근거는?
동전은 같은 종류를 몇 개든 쓸 수 있고, 금액을 내는 방법은 동전을 더하는 것뿐이다. 그래서 x − c원을 내는 어떤 방법에 c 하나를 더하면 늘 x원이 된다. 앞의 선택이 뒤의 선택을 제한하지 않는다는 것이 여기서 쓰인다.
2. 기억하기를 붙인 피보나치가 59번만 부르는 까닭은?
f(k)의 실제 계산은 k = 0 ~ 30에서 한 번씩, 31번이다. 계산마다 f(k − 1)과 f(k − 2)를 부르는데, 둘 중 먼저 부른 쪽이 계산을 이어 가고 나중 것은 표에서 바로 꺼낸다. 그래서 부르는 횟수는 계산 31번에 표에서 꺼내는 28번을 더한 59번이다.
3. 아래에서부터 채울 때 x를 1부터 올라가야 하는 까닭은?
dp[x]를 구할 때 dp[x − c]를 읽는다. x − c < x이니 작은 금액부터 채우면 읽을 칸이 늘 먼저 채워져 있다. 계산 순서는 “점화식이 읽는 칸이 먼저”가 되도록 정한다.
이 방법의 핵심 아이디어는?
가장 좋은 답의 “마지막 선택”을 모두 따져 보고, 나머지는 이미 구한 작은 문제의 답으로 채운다. 같은 작은 문제는 표에서 꺼내 한 번만 푼다.
같은 방법을 쓸 수 있는 다른 상황은?
격자에서 오른쪽·아래로만 가는 최소 비용 길(마지막 칸에 위에서 왔나 왼쪽에서 왔나), 배낭 문제(마지막 물건을 넣었나 안 넣었나), 두 문자열의 편집 거리, 그리고 플로이드–워셜(마지막으로 허락한 점 k를 거쳤나 안 거쳤나)이 모두 같은 모양이다.
적용 조건과 알아보는 신호
- 조건: 최적 부분 구조가 있고, 부분 문제가 겹치며, 상태의 개수가 표에 담을 만큼 작다.
- 신호: “가짓수를 구하라”, “최소·최대 비용”, “~할 수 있는가”인데 선택이 이어지고, 완전탐색은 경우가 너무 많으며, 그리디는 반례가 있다.
- 비용: (상태 수) × (상태 하나를 채우는 비용)이다. 동전 문제는 금액 X, 동전 K종이면 \(O(XK)\)다.
- 대표 문제: 코딩 테스트 공부는 (알고력, 코딩력)을 상태로 최소 시간을, 도둑질은 (집 번호, 첫 집을 털었나)를 상태로 최대 금액을 구한다.
- 연습 순서: 동적 계획법 예제 사다리
활용
- 쓰는 곳: 문서 비교 도구의 차이 찾기와 맞춤법 검사의 편집 거리, 생물정보학의 서열 정렬, 최단 경로(벨만–포드, 플로이드–워셜)가 모두 DP다4.
- 메모리 줄이기: dp[x]가 바로 앞 몇 칸만 읽으면 그 칸만 남긴다. 배낭 문제는 1차원 표 하나를 큰 쪽부터 채워 공간을 \(O(W)\)로 줄인다(확인 문제 C4).
- 흔한 실수: 상태의 뜻을 정하지 않고 점화식부터 쓴다. 상태에 필요한 정보를 빠뜨린다(예: 방향, 마지막 선택). 시작값을 0과 무한대 중 잘못 고른다. 파이썬에서 위에서부터 방식으로 깊이 수천의 재귀를 돌려
RecursionError가 난다.
연결
- 선수: 재귀와 백트래킹, 선형 점화식
- 대조: 그리디는 선택 하나만 믿고, DP는 모든 선택을 따진 뒤 가장 좋은 것을 고른다.
- 완전탐색·백트래킹에 “같은 부분 문제는 한 번만”을 더한 것이 위에서부터 DP다.
- “점화식이 읽는 칸이 먼저”인 계산 순서는 칸 사이 의존 관계의 위상 정렬이다. 의존이 고리를 이루면 칸을 한 번씩 채워 표를 완성하는 순서가 아예 없다.
- 그대로 재귀로 f(n)을 구하면 함수를 2f(n + 1) − 1번 부른다(f(0) = 0, f(1) = 1). n = 30이면 f(31) = 1,346,269라서 위 예시의 호출 수가 그대로 나온다. 이 식은 재귀적 정의와 구조적 귀납법의 “재귀의 비용”에 있다.
- 신경망의 역전파도 동적 계획법이다. 노드마다 “출력이 이 값에 얼마나 민감한가”를 표의 칸으로 두고, 출력 쪽부터 한 번씩만 채운다. 그래서 입력에서 출력까지 가는 길의 수가 층마다 곱해져 아주 많아도, 계산은 간선 수에 비례한다(연쇄 법칙 ↔ 역전파).
- 피보나치처럼 앞 칸들에 상수를 곱해 더하는 DP는 “벡터에 같은 행렬을 곱하기”를 되풀이하는 것과 같다(선형 점화식 ↔ 행렬 거듭제곱). 그 행렬을 제곱해 나가면 행렬 곱 \(O(\log n)\)번으로 n번째 칸이 나온다. 동전 문제처럼 min이나 max가 든 점화식은 보통의 행렬 곱으로 쓸 수 없다.
- 함께 보면 좋은 수학: 금액을 내는 방법의 수는 동전 종류마다 한 바퀴씩
dp[x] += dp[x - c]를 돌려 센다. 이 한 바퀴는 생성함수에서 c원 동전의 인수를 하나 곱하는 일이다. 단계마다 같은 규칙으로 상태를 옮기며 가짓수를 세는 표는 한 줄을 채울 때마다 상태 그래프의 인접행렬을 한 번 곱한다(인접행렬 거듭제곱 ↔ 마르코프 전이). 최솟값 대신 확률로 가중평균하면 기댓값 DP가 되고, 그 근거는 결합분포와 조건부 기댓값의 아담의 법칙이다. - 브리지: 위상 정렬 ↔ 동적 계획법의 계산 순서
- 연습: 코딩 테스트 공부
자주 하는 오해
틀렸다. 기억하기는 같은 부분 문제가 다시 나올 때만 이득이다. 리스트를 반으로 나눠 더하는 재귀는 같은 구간을 두 번 부르지 않는다. 원소 64개에서 기억하기를 붙여도 호출은 똑같이 127번이고, 표만 쓸데없이 늘어난다. 순열을 모두 만드는 백트래킹도 경로마다 상태가 달라 겹침이 없다. 거꾸로, 상태에 “지금까지 고른 것 전부”처럼 큰 정보를 넣으면 겹침이 거의 없어져 표가 폭발한다. 확인하려면 “서로 다른 상태의 수”와 “호출 수”를 세어 비교하면 된다. 호출 수가 상태 수보다 훨씬 많을 때만 기억하기가 이득이다.
확인 문제
C1 동전이 1원, 5원, 6원, 9원일 때 11원을 내는 최소 개수를 DP로 구하라. 그리디(큰 동전부터)의 답과 비교하라.
답: DP는 2개(5 + 6)다. dp[11] = min(dp[10], dp[6], dp[5], dp[2]) + 1이고 dp[6] = dp[5] = 1이라 2다. 그리디는 9 + 1 + 1로 3개다.
C2 피보나치 f(30)을 그대로 재귀로 구하면 함수를 약 270만 번 부르는데, 기억하기를 붙이면 59번으로 주는 까닭은?
답: 그대로 재귀는 f(k)를 부를 때마다 다시 계산해, 호출 수가 f(n)처럼 거의 1.6배씩 불어난다. 기억하기를 붙이면 서로 다른 부분 문제 f(0) ~ f(30) 31개를 한 번씩만 계산하고, 나머지 호출은 표에서 꺼내고 바로 끝난다.
C3 동전 점화식 증명에서 “가장 적게 내는 방법에서 마지막 동전 c를 뗀 나머지는 x − c원을 가장 적게 내는 방법이다”는 어떻게 정당화하는가?
답: 잘라 붙이기 논증이다. 나머지가 최소가 아니라면 x − c원을 더 적게 내는 방법이 있다. 거기에 c를 붙이면 x원을 원래보다 적게 내게 되어, 원래 방법이 최소라는 가정에 모순이다.
C4 0-1 배낭(물건마다 한 번만 넣기)을 1차원 표로 풀 때 for cap in range(w, W + 1)(작은 쪽부터)로 돌리면 틀리는 예를 들어라.
답: 물건 하나(무게 2, 값 3), 배낭 4. 작은 쪽부터 돌리면 dp[2] = 3을 채운 뒤 같은 바퀴에서 dp[4] = dp[2] + 3 = 6이 된다. 같은 물건을 두 번 넣은 셈이다. 답은 3이다. 큰 쪽부터 돌리면 dp[4]를 계산할 때 dp[2]가 아직 이번 물건을 반영하지 않아 한 번만 넣는다.
-
‘같은 계산의 반복’ 절의 피보나치 재귀 f(n) = f(n − 1) + f(n − 2)(f(0) = 0, f(1) = 1)를 n = 4에서 호출 나무로 그렸다. 호출 9번은 ‘연결’ 절의 공식 2f(n + 1) − 1 = 2 · 5 − 1과 같다. ↩
-
30_dynamic-programming_plot.py로 그렸고, f(30)에서 2,692,537번과 59번, 부르는 횟수를 점화식(횟수 = 1 + 앞 두 횟수의 합)으로 센 값이 실제로 센 값과 같다는 것(n ≤ 20), 표에 적으면 2n − 1번이라는 것을 같은 코드로 확인했다. ↩
-
최적 부분 구조와 겹치는 부분 문제, 잘라 붙이기 논증은 Cormen 외, Introduction to Algorithms 3판, 15.3절 “Elements of dynamic programming”. 동전 문제의 점화식과 기억하기는 Laaksonen, Competitive Programmer’s Handbook (2018년 7월판), 7.1 “Coin problem”. ↩
-
편집 거리는 같은 책 7.5 “Edit distance”, 벨만–포드와 플로이드–워셜은 13.1·13.3절. 맞춤법 교정과 DNA 서열 비교에 편집 거리를 쓰는 것은 위키백과 “Edit distance” 항목(Wagner–Fischer 동적 계획법)에, 문서 비교 도구 diff가 최장 공통 부분 수열 문제를 푼다는 것은 Hunt & McIlroy(1976) “An Algorithm for Differential File Comparison”과 위키백과 “Diff” 항목에 있다. ↩