동적계획법(Dynamic Programming, DP)은 특정 알고리즘의 명칭이 아니라, 복잡한 최적화 문제를 해결하기 위한 강력하고 일반적인 설계 패러다임(Design Paradigm)이다.1 이 접근법의 핵심은 주어진 문제를 해결 가능한 더 작은 크기의 여러 부분 문제(subproblem)들로 분해하고, 각 부분 문제의 해를 한 번만 계산하여 그 결과를 저장(memoization)한 뒤, 필요할 때마다 재활용함으로써 전체 문제의 최적해를 효율적으로 도출하는 데 있다.3
‘동적계획법’이라는 명칭은 알고리즘의 실제 동작 방식과 직관적으로 연결되지 않을 수 있다. 이는 이 방법론의 창시자인 리처드 벨만(Richard Bellman)이 1950년대 연구 자금을 지원받는 과정에서, 자신의 연구가 다단계 의사결정 과정의 계획(planning)을 다룬다는 점을 강조하고, ‘Dynamic’이라는 단어가 주는 긍정적이고 진취적인 인상을 활용하기 위해 의도적으로 선택한 이름이라는 역사적 배경이 있다.5 따라서 이 용어 자체에 얽매이기보다는, 그 이면에 담긴 수학적 원리와 문제 해결 철학을 이해하는 것이 본질에 접근하는 길이다.
본 보고서는 동적계획법을 다각적으로 고찰하는 것을 목표로 한다. 제1장에서는 동적계획법이 성립하기 위한 두 가지 핵심 조건인 ‘최적 부분 구조’와 ‘중복되는 부분 문제’를 심도 있게 분석한다. 제2장에서는 이를 구현하는 대표적인 두 가지 전략, 즉 하향식 메모이제이션과 상향식 타뷸레이션을 비교 탐구한다. 제3장에서는 최장 공통 부분 수열(LCS), 0/1 배낭 문제, 플로이드-워셜 알고리즘과 같은 고전적인 문제들을 통해 동적계획법의 원리가 실제 어떻게 적용되는지를 상세히 해부한다. 제4장에서는 분할 정복, 탐욕 알고리즘 등 다른 주요 알고리즘 패러다임과의 비교를 통해 동적계획법의 고유한 위상과 특징을 명확히 규명한다. 마지막으로 제5장에서는 동적계획법의 현대적 응용 분야를 조망하고, ‘차원의 저주’라는 근본적 한계와 이를 극복하려는 시도들을 논하며 그 현재적 의의를 고찰한다.
동적계획법은 모든 문제에 적용할 수 있는 만능 해결책이 아니다. 이 패러다임이 성공적으로 적용되기 위해서는 해결하고자 하는 문제가 반드시 두 가지 핵심적인 구조적 속성을 만족해야 한다. 이 두 조건은 단순히 적용 가능 여부를 확인하는 체크리스트를 넘어, 특정 유형의 문제 구조를 식별하고 동적계획법적 사고를 시작하게 하는 렌즈 역할을 한다.
최적 부분 구조란 문제의 최적해가 그 문제를 구성하는 부분 문제들의 최적해로부터 효율적으로 구성될 수 있는 구조적 속성을 의미한다.3 다시 말해, 전체 문제에 대한 최적의 결정은 그 결정으로 인해 파생되는 모든 부분 문제들에 대해서도 여전히 최적의 결정을 포함해야 한다는 원리이다. 이는 리처드 벨만이 제시한 ‘최적성의 원리(Principle of Optimality)’와 직접적으로 연결된다.
이 속성을 이해하기 위해 대표적인 예시를 살펴보자.
이처럼 최적 부분 구조는 문제를 더 작은 단위로 분해하여 해결할 수 있는 가능성을 열어주는 근본적인 전제 조건이다.
중복되는 부분 문제란, 문제를 재귀적으로 분해하는 과정에서 동일한 형태의 부분 문제가 여러 번 반복적으로 나타나는 속성을 말한다.8 이 속성이야말로 동적계획법이 단순 재귀 호출이나 분할 정복 알고리즘에 비해 압도적인 효율성을 갖게 하는 핵심적인 이유다. 동적계획법의 진가는 바로 이 ‘중복’을 ‘기억’을 통해 ‘재활용’으로 전환하는 데서 발현된다.3
이 속성은 피보나치 수열의 재귀 호출 트리를 통해 시각적으로 명확히 확인할 수 있다. 예를 들어, $f(5)$를 계산하는 과정을 살펴보자.
f(5)
/ \
f(4) f(3)
/ \ / \
f(3) f(2) f(2) f(1)
/ \ / \ / \
f(2) f(1) f(1)f(0)f(1)f(0)
/ \
f(1)f(0)
위 호출 트리에서 볼 수 있듯이, $f(3)$은 2번, $f(2)$는 3번, $f(1)$은 5번 호출된다. $n$의 크기가 커질수록 이러한 중복 호출의 수는 지수적으로 증가하여 심각한 비효율을 초래한다.4 동적계획법은 각 부분 문제(예: $f(3)$)의 해를 최초 계산 시 저장해두었다가, 이후 동일한 문제가 나타나면 저장된 값을 즉시 반환하여 이러한 중복 계산을 원천적으로 차단한다.
반면, 합병 정렬(Merge Sort)과 같은 분할 정복 알고리즘은 최적 부분 구조를 가지지만 중복되는 부분 문제가 발생하지 않는다. 크기가 8인 배열을 정렬할 때, 이를 크기가 4인 두 개의 배열로 나누어 각각 정렬한다. 이 두 부분 문제, 즉 ‘왼쪽 절반 정렬’과 ‘오른쪽 절반 정렬’은 서로 완전히 독립적이며, 처리하는 데이터 범위가 겹치지 않아 동일한 부분 문제가 반복될 여지가 없다.3 따라서 이러한 경우에는 동적계획법을 적용할 실익이 없다.
결론적으로, 이 두 조건의 관계를 깊이 이해하는 것이 중요하다. ‘최적 부분 구조’는 문제를 분해할 수 있는 가능성을 타진하는 첫 단계이며, 이 분해의 결과로 나타나는 ‘현상’이 바로 ‘중복되는 부분 문제’이다. 이 현상이 관찰될 때, 비로소 동적계획법이라는 강력한 도구를 사용할 명확한 이유가 생기는 것이다.
동적계획법의 원리를 실제 코드로 구현하는 데에는 크게 두 가지 대표적인 방법론이 존재한다. 이는 단순히 코딩 스타일의 차이를 넘어, 문제 해결에 대한 접근 철학의 차이를 반영하며 각각의 장단점이 뚜렷하다.
메모이제이션은 큰 문제에서 시작하여 재귀 호출을 통해 더 작은 문제로 자연스럽게 내려가는 하향식 접근법이다.11 이 전략의 핵심은 계산된 부분 문제의 결과를 캐시(cache, 보통 배열이나 해시맵)에 저장하는 것이다. 어떤 부분 문제를 풀어야 할 때, 먼저 캐시에 해당 문제의 해가 이미 저장되어 있는지 확인한다. 만약 값이 존재하면 계산 과정 없이 즉시 반환하고, 존재하지 않을 경우에만 재귀적으로 문제를 풀어 그 결과를 캐시에 저장한 후 반환한다. 이는 필요한 부분 문제만 계산하는 ‘지연 평가(Lazy Evaluation)’ 방식으로 동작한다.13
피보나치 수열을 메모이제이션 방식으로 구현한 파이썬 코드는 다음과 같다.
# DP memoization (하향식)
memo = * 101 # 결과를 저장할 캐시, 0으로 초기화
def fib_memo(n):
# 기저 사례
if n <= 1:
return n
# 캐시에 계산된 값이 있는지 확인
if memo[n]!= 0:
return memo[n]
# 계산된 값이 없으면 재귀 호출 후 결과를 캐시에 저장
memo[n] = fib_memo(n-1) + fib_memo(n-2)
return memo[n]
이 방식은 문제의 점화식을 코드로 거의 그대로 옮길 수 있어 매우 직관적이라는 장점이 있다.11 하지만 재귀 호출의 깊이가 시스템이 허용하는 한계를 초과할 경우 스택 오버플로(Stack Overflow) 오류가 발생할 수 있으며, 반복적인 함수 호출에 따른 미세한 오버헤드가 존재한다.11
타뷸레이션은 가장 작은 문제, 즉 기저 사례(base case)에서부터 시작하여 문제의 크기를 점차 키워나가는 상향식 접근법이다.11 이 전략은 반복문(iteration)을 사용하여 DP 테이블(table)을 순서대로 채워나간다. 하위 문제의 해를 먼저 계산하고, 이 결과를 이용하여 상위 문제의 해를 도출하는 과정을 반복하여 최종적으로 목표하는 문제의 해에 도달한다. 이는 관련된 모든 부분 문제를 미리 계산하는 ‘조기 평가(Eager Evaluation)’ 방식으로 동작한다.12
피보나치 수열을 타뷸레이션 방식으로 구현한 파이썬 코드는 다음과 같다.
# DP 타뷸레이션 (상향식)
def fib_tab(n):
dp = * (n + 1) # DP 테이블 생성
if n >= 1:
dp = 1
# 가장 작은 문제부터 테이블을 채워나감
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
이 방식은 재귀를 사용하지 않으므로 스택 오버플로의 위험이 없으며, 함수 호출 오버헤드가 없어 일반적으로 메모이제이션 방식보다 약간 더 빠른 성능을 보인다.11 그러나 문제 해결에 필요하지 않은 부분 문제까지 모두 계산할 수 있다는 단점이 있으며, 때로는 문제 해결의 순서를 직접 설계해야 하므로 하향식보다 덜 직관적으로 느껴질 수 있다.11
두 전략의 선택은 단순한 개인의 선호도를 넘어 16, 해결하고자 하는 문제의 구조적 특성, 특히 ‘상태 공간(State Space)의 밀도’에 대한 깊은 이해를 바탕으로 한 전략적 결정이어야 한다. 동적계획법 문제는 결국 상태 공간을 탐색하는 문제로 귀결된다. 만약 문제의 최적해를 구하기 위해 상태 공간의 거의 모든 점(부분 문제)을 방문해야 하는 ‘밀집(dense)’한 구조라면, 모든 점을 체계적으로 방문하는 타뷸레이션 방식이 불필요한 계산 없이 효율적이다. 반면, 최적해가 상태 공간의 특정 경로에만 의존하고 대부분의 상태는 방문할 필요가 없는 ‘희소(sparse)’한 구조라면, 필요한 점만 골라서 방문하는 메모이제이션 방식이 불필요한 계산을 피해 더 효율적일 수 있다. 따라서 어떤 방식을 선택할 것인가는 “이 문제의 상태 공간은 밀집한가, 희소한가?”라는 더 근본적인 질문에 대한 답을 찾는 과정이며, 이는 설계자의 문제 이해도를 반영하는 척도가 된다.
다음 표는 두 전략의 핵심적인 차이점을 요약한 것이다.
| 구분 | 메모이제이션 (하향식) | 타뷸레이션 (상향식) |
|---|---|---|
| 접근 방향 | 큰 문제에서 작은 문제로 재귀적 분해 | 가장 작은 문제에서 큰 문제로 점진적 구축 |
| 핵심 원리 | 지연 평가 (Lazy Evaluation): 필요할 때 계산 | 조기 평가 (Eager Evaluation): 미리 모두 계산 |
| 구현 수단 | 재귀 함수 + 캐시 (배열, 해시맵) | 반복문 (for, while) + DP 테이블 (배열) |
| 장점 | - 점화식을 그대로 코드로 옮기기 용이하여 직관적 11 - 필요한 부분 문제만 계산함 12 |
- 재귀 깊이 제한 및 스택 오버플로 위험 없음 11 - 함수 호출 오버헤드가 없어 일반적으로 더 빠름 13 - 메모리 최적화(예: 공간 복잡도 $O(N)$ → $O(1)$)가 용이함 |
| 단점 | - 재귀 호출로 인한 스택 오버플로 가능성 11 - 함수 호출 오버헤드 발생 |
- 불필요한 부분 문제까지 모두 계산할 수 있음 12 - 문제 해결 순서를 직접 설계해야 하므로 덜 직관적일 수 있음 |
동적계획법의 원리가 실제 문제 해결에 어떻게 적용되는지를 이해하기 위해, 세 가지 고전적인 대표 문제를 심층적으로 분석한다. 각 문제에 대해 문제 정의, 상태 정의, 점화식 도출, DP 테이블 구축, 복잡도 분석의 일관된 프레임워크를 적용하여 동적계획법적 사고 과정을 체계적으로 탐구한다.
최장 공통 부분 수열(LCS) 문제는 두 개의 수열(또는 문자열)이 주어졌을 때, 두 수열 모두에 포함되는 부분 수열 중 가장 긴 것의 길이를 찾는 문제다.17 여기서 ‘부분 수열(subsequence)’은 원래 수열에서 0개 이상의 원소를 제거하여 얻을 수 있는 수열로, 원소들의 상대적 순서는 유지되어야 하지만 연속적일 필요는 없다는 점이 ‘부분 문자열(substring)’과의 핵심적인 차이점이다.19
동적계획법 문제 해결에서 가장 창의적이고 중요한 단계는 ‘상태(state)’를 올바르게 정의하는 것이다.21 LCS 문제에서 상태는 2차원 DP 테이블 $DP[i][j]$로 정의할 수 있으며, 그 의미는 다음과 같다:
상태 $DP[i][j]$는 더 작은 부분 문제들의 해, 즉 테이블의 이전 값들로부터 계산될 수 있다. 두 수열을 각각 $X = x_1x_2…x_m$과 $Y = y_1y_2…y_n$이라 할 때, $DP[i][j]$를 계산하는 규칙은 현재 비교하는 두 원소 $x_i$와 $y_j$가 같은지 여부에 따라 나뉜다.
x_i = y_j일 경우:
두 원소가 같다면, 이 원소는 공통 부분 수열에 포함될 수 있다. 따라서 현재의 LCS 길이는 x_i와 y_j를 제외한 나머지 부분, 즉 X_{1..i-1}과 Y_{1..j-1}의 LCS 길이에 1을 더한 것과 같다.17
DP[i][j] = DP[i-1][j-1] + 1
x_i \neq y_j일 경우:
두 원소가 다르다면, 둘 중 하나는 현재 LCS에 포함될 수 없다. 따라서 두 가지 경우를 고려해야 한다: (1) x_i를 제외하고 X_{1..i-1}과 Y_{1..j}의 LCS를 구하는 경우, (2) y_j를 제외하고 X_{1..i}와 Y_{1..j-1}의 LCS를 구하는 경우. 이 두 경우 중 더 긴 쪽이 DP[i][j]의 값이 된다.19
DP[i][j] = \max(DP[i-1][j], DP[i][j-1])
이를 종합한 점화식은 다음과 같다. \(DP[i][j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \\ DP[i-1][j-1] + 1 & \text{if } X_i = Y_j \\ \max(DP[i-1][j], DP[i][j-1]) & \text{if } X_i \neq Y_j \end{cases}\)
예를 들어, 두 문자열 “ACAYKP”와 “CAPCAK”의 LCS를 구하는 과정을 살펴보자. $m \times n$ 크기의 DP 테이블을 생성하고, 위 점화식에 따라 좌상단에서 우하단으로 테이블을 채워나간다.17
| C | A | P | C | A | K | ||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| C | 0 | 1 | 1 | 1 | 2 | 2 | 2 |
| A | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| Y | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| K | 0 | 1 | 2 | 2 | 2 | 3 | 4 |
| P | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
테이블의 마지막 셀 $DP[m][n]$에 있는 값 4가 LCS의 길이가 된다. 실제 LCS 문자열을 찾기 위해서는 이 마지막 셀에서부터 역으로 경로를 추적(backtracking)해야 한다. $DP[i][j]$의 값이 대각선 위 $DP[i-1][j-1]$에서 왔다면 해당 문자 $X_i$($Y_j$)가 공통 문자에 해당하며, 위쪽이나 왼쪽에서 왔다면 해당 문자를 건너뛰고 값이 같은 방향으로 이동한다. 이 과정을 통해 “ACAK”라는 LCS를 복원할 수 있다.19
두 수열의 길이를 각각 $m$과 $n$이라 할 때, $m \times n$ 크기의 테이블을 한 번씩 채워야 하므로 시간 복잡도는 $O(mn)$이다. 테이블을 저장하기 위한 공간 복잡도 역시 $O(mn)$이다.19
0/1 배낭 문제는 각각 다른 무게(weight)와 가치(value)를 가지는 $N$개의 아이템과, 최대 수용 무게가 $K$로 정해진 배낭이 있을 때, 배낭에 담는 아이템들의 가치 합이 최대가 되도록 하는 조합을 찾는 최적화 문제다.23 ‘0/1’이라는 제약은 각 아이템을 통째로 담거나(1) 아예 담지 않거나(0) 둘 중 하나만 선택할 수 있음을 의미하며, 아이템을 쪼갤 수 없다.24 이 제약 조건 때문에, 단위 무게당 가치가 가장 높은 아이템부터 담는 탐욕적 접근법은 최적해를 보장하지 못하며, 동적계획법이 필요하다.23
이 문제의 상태는 ‘고려한 아이템’과 ‘현재 배낭의 허용 무게’라는 두 가지 변수로 정의할 수 있다.
$DP[i][w]$를 계산하기 위해서는 $i$번째 아이템에 대한 결정을 내려야 한다: 이 아이템을 배낭에 넣을 것인가, 말 것인가? 26
i번째 아이템을 넣지 않는 경우:
이 경우의 최대 가치는 i번째 아이템을 고려 대상에서 제외하고, 1부터 i-1번째 아이템까지를 가지고 허용 무게 w를 채웠을 때의 최대 가치와 같다.
\(DP[i-1][w]\)
$i$번째 아이템을 넣는 경우:
이 선택은 $i$번째 아이템의 무게 $w_i$가 현재 허용 무게 $w$보다 작거나 같을 때만 가능하다. 만약 넣는다면, 최대 가치는 $i$번째 아이템의 가치 $v_i$에, 남은 $i-1$개의 아이템으로 남은 허용 무게 $w - w_i$를 채웠을 때의 최대 가치를 더한 값이 된다. \(v_i + DP[i-1][w - w_i]\) DP[i][w]$는 위 두 가지 선택지 중 더 큰 가치를 제공하는 쪽을 선택한 결과이다.7 이를 종합한 점화식은 다음과 같다.
$N \times K$ 크기의 2차원 테이블을 생성하고, 아이템을 하나씩 늘려가며(행) 각 허용 무게에(열) 대한 최대 가치를 계산하여 테이블을 채운다.25 최종적으로 $DP[N][K]$가 문제의 답, 즉 $N$개의 아이템을 모두 고려하고 최대 허용 무게가 $K$일 때의 최대 가치가 된다.
테이블의 크기가 $(N+1) \times (K+1)$이므로, 시간 복잡도와 공간 복잡도는 모두 $O(NK)$이다. 여기서 주목할 점은 시간 복잡도가 입력값의 크기($N$)뿐만 아니라 입력값 자체($K$)에도 의존한다는 것이다. 만약 $K$가 매우 큰 수라면 계산 시간이 급격히 증가하므로, 이를 의사 다항 시간(pseudo-polynomial time) 복잡도라고 부른다.
플로이드-워셜 알고리즘은 그래프의 ‘모든 정점 쌍’ 간의 최단 경로를 찾는 알고리즘으로, 동적계획법의 원리를 기반으로 한다.28 이 알고리즘의 핵심 아이디어는 경유할 수 있는 정점의 집합을 점진적으로 늘려가며 최단 경로를 갱신하는 것이다.
플로이드-워셜 알고리즘의 상태는 ‘허용된 경유지’라는 개념을 통해 정의할 수 있다.
D[k][i][j] : 정점 집합 ${1, 2,…, k}$에 속한 정점들만을 중간 경유지로 사용했을 때, 정점 $i$에서 정점 $j$로 가는 최단 경로의 길이.D[k][i][j]를 계산하기 위해서는, 정점 $k$를 경유지로 포함시킬지 여부를 결정해야 한다.
정점 $k$를 경유하지 않는 최단 경로:
이 경로는 $1$부터 $k-1$까지의 정점들만 경유지로 사용하므로, 그 길이는 D[k-1][i][j]이다.
정점 $k$를 경유하는 최단 경로:
이 경로는 $i \rightarrow… \rightarrow k \rightarrow… \rightarrow j$ 형태를 띤다. 최적 부분 구조에 의해, 이 경로의 길이는 i에서 k까지 가는 최단 경로와 k에서 j까지 가는 최단 경로의 합과 같다. 이때 두 부분 경로는 1부터 k-1까지의 정점만 경유지로 사용해야 한다. 따라서 그 길이는 D[k-1][i][k] + D[k-1][k][j]이다.
D[k][i][j]는 위 두 경로 중 더 짧은 쪽의 길이를 택한 결과이다.
\(D[k][i][j] = \min(D[k-1][i][j], D[k-1][i][k] + D[k-1][k][j])\)
실제 구현에서는 3차원 배열 대신 2차원 배열 하나만 사용하여 공간을 최적화한다. $k$에 대한 루프가 가장 바깥쪽에 위치하면 $D[i][j]$를 갱신할 때 사용되는 $D[i][k]$와 $D[k][j]$는 이미 $k$번째 단계의 갱신이 완료된 값이므로, 점화식은 다음과 같이 단순화된다.31
\(D[i][j] = min(D[i][j], D[i][k] + D[k][j])\)
알고리즘은 인접 행렬로 표현된 그래프에서 시작한다. 연결된 간선은 가중치로, 연결되지 않은 경로는 무한대($\infty$)로, 자기 자신으로의 경로는 0으로 초기화한다. 그 후, 경유지 $k$를 1부터 $N$까지, 출발지 $i$를 1부터 $N$까지, 도착지 $j$를 1부터 $N$까지 순회하는 3중 반복문을 실행하며 위 점화식에 따라 최단 경로 테이블을 계속 갱신한다.31 3중 반복문 구조로 인해 시간 복잡도는 명확하게 $O(V^3)$이며, 여기서 $V$는 정점의 개수다.31
이 세 가지 대표 문제를 통해 드러나는 공통적인 핵심은, 동적계획법의 본질이 단순히 공식을 암기하여 적용하는 기계적인 과정이 아니라는 점이다. 오히려 문제의 구조를 깊이 분석하여 ‘최적 부분 구조’를 드러낼 수 있는 ‘상태’를 창의적으로 정의하고, 그 상태들 사이의 ‘전이 관계’를 논리적인 점화식으로 표현하는 지적인 활동에 가깝다. LCS, 배낭 문제, 플로이드-워셜은 각기 다른 맥락의 문제처럼 보이지만, 그 해결의 중심에는 이 ‘상태 정의의 기술’이라는 동일한 심장이 뛰고 있다.
동적계획법의 고유한 특성과 위치를 명확히 이해하기 위해서는, 다른 주요 알고리즘 설계 패러다임과의 비교가 필수적이다. 특히 분할 정복과 탐욕 알고리즘은 동적계획법과 공통점을 공유하면서도 결정적인 차이를 보여, 그 본질을 파악하는 데 중요한 기준점을 제공한다.
동적계획법과 분할 정복은 모두 큰 문제를 해결 가능한 작은 부분 문제들로 나누어 해결한다는 점에서 근본적인 철학을 공유한다. 두 패러다임 모두 문제에 ‘최적 부분 구조’가 존재할 때 적용 가능하다는 공통점을 가진다.33
두 패러다임을 가르는 가장 결정적인 차이는 ‘부분 문제의 중복성’ 여부다.35
결론적으로, 분할 정복은 ‘분할 후 독립적으로 정복하고 통합’하는 방식이라면, 동적계획법은 ‘분할 후 의존적인 부분 문제들의 해를 기억하며 정복’하는 방식이라 할 수 있다.
탐욕 알고리즘 역시 동적계획법과 마찬가지로 ‘최적 부분 구조’를 가지는 문제에 적용될 수 있다.36 즉, 전체 문제의 최적해가 부분 문제의 최적해로부터 도출될 수 있는 구조를 전제로 한다.
두 패러다임의 근본적인 차이는 ‘선택의 방식’과 ‘전역 최적해 보장 여부’에 있다.
이 차이는 ‘거스름돈 문제’ 예시를 통해 명확히 드러난다.
다음 표는 세 가지 알고리즘 패러다임의 핵심적인 특징을 비교 분석한 것이다.
| 구분 | 동적계획법 (DP) | 분할 정복 (Divide & Conquer) | 탐욕 알고리즘 (Greedy) |
|---|---|---|---|
| 핵심 아이디어 | 부분 문제의 해를 저장하고 재활용 | 문제를 분할하여 각각 해결 후 통합 | 매 순간 가장 좋아 보이는 것을 선택 |
| 필요 조건 | 1. 최적 부분 구조 2. 중복되는 부분 문제 | 1. 최적 부분 구조 | 1. 최적 부분 구조 2. 탐욕적 선택 속성 |
| 부분 문제 | 서로 의존적이며, 중복 발생 34 | 서로 독립적이며, 중복 없음 34 | 하위 문제들이 독립적 2 |
| 접근 방식 | 모든 가능성을 고려하여 전역 최적해 도출 | 재귀적 분할 및 정복 | 근시안적 선택의 연속 33 |
| 전역 최적해 | 보장 | 보장 | 보장하지 않음 (특수한 경우에만) |
| 대표 예시 | LCS, 0/1 배낭 문제, 피보나치 수열 | 합병 정렬, 퀵 정렬, 이진 탐색 | 최소 신장 트리(Prim, Kruskal), 다익스트라, 일부 거스름돈 문제 |
동적계획법은 컴퓨터 과학의 고전적인 알고리즘 문제를 넘어, 현대 과학 및 공학의 다양한 분야에서 복잡한 최적화 문제를 해결하는 데 핵심적인 역할을 하고 있다. 그러나 동시에, 그 적용 범위를 제한하는 근본적인 한계 또한 명확히 존재한다. 이 장에서는 동적계획법의 현대적 응용 사례와 그 치명적인 한계인 ‘차원의 저주’, 그리고 이를 극복하기 위한 시도들을 조망한다.
동적계획법의 강력함에도 불구하고, 이 패러다임은 치명적인 한계를 내포하고 있는데, 바로 ‘차원의 저주’이다.42 이는 문제의 상태를 정의하는 변수, 즉 ‘차원’의 수가 증가함에 따라, 상태 공간(state space)의 크기가 지수적으로 폭증하여 계산에 필요한 시간과 메모리가 현실적으로 감당할 수 없는 수준에 이르는 현상을 의미한다.
예를 들어, 어떤 상태가 10개의 이산적인 값을 가질 수 있는 변수 하나로 정의된다면 상태 공간의 크기는 10이다. 하지만 변수가 2개로 늘어나면 상태 공간은 $10^2 = 100$이 되고, 변수가 10개라면 $10^{10}$개의 상태가 존재하게 된다. 동적계획법의 타뷸레이션 방식은 이 모든 상태에 대한 값을 저장할 테이블을 필요로 하므로, 차원이 조금만 증가해도 메모리 요구량이 천문학적으로 늘어난다.
또한, 고차원 공간에서는 데이터의 희소성(sparsity) 문제가 발생한다.44 제한된 수의 데이터 포인트는 고차원 공간에 흩어져 서로 간의 거리가 매우 멀어지게 되며, 이로 인해 유의미한 패턴을 학습하거나 정확한 가치를 추정하기가 극도로 어려워진다.46 이러한 이유로, 체스나 바둑처럼 상태 변수가 매우 많은 복잡한 문제에 전통적인 동적계획법을 직접 적용하는 것은 불가능하다.
‘차원의 저주’라는 근본적인 한계는 동적계획법의 종말을 의미하는 것이 아니라, 오히려 새로운 패러다임의 탄생을 촉발한 지적 원동력이 되었다. 이는 ‘정확성(Exactness)’과 ‘확장성(Scalability)’ 사이의 근본적인 트레이드오프를 어떻게 다룰 것인가에 대한 고민으로 이어졌으며, 고전 알고리즘과 현대 인공지능을 가르는 중요한 분수령이 되었다.
본 보고서는 동적계획법을 문제 해결 패러다임으로서 다각적으로 분석하였다. 제1장에서는 동적계획법이 성립하기 위한 두 가지 핵심 조건, ‘최적 부분 구조’와 ‘중복되는 부분 문제’가 상호 유기적인 관계 속에서 동적계획법의 필요성을 규정함을 밝혔다. 제2장에서는 하향식 메모이제이션과 상향식 타뷸레이션이라는 두 구현 전략이 단순한 코딩 스타일의 차이를 넘어 문제의 상태 공간 밀도에 따른 전략적 선택임을 논하였다. 제3장에서는 LCS, 0/1 배낭 문제, 플로이드-워셜 알고리즘 등 대표적인 문제 분석을 통해, 문제의 본질을 꿰뚫는 ‘상태 정의’와 ‘상태 전이 관계’ 모델링이 동적계획법의 핵심임을 확인하였다. 제4장에서는 분할 정복 및 탐욕 알고리즘과의 비교를 통해 동적계획법의 고유한 위치와 전역 최적해를 보장하는 강력함을 규명하였다. 마지막으로 제5장에서는 생물정보학, 경제학 등 다양한 분야로의 확장을 조망하는 한편, ‘차원의 저주’라는 근본적 한계가 어떻게 근사 동적계획법과 강화학습이라는 새로운 지평을 열었는지를 탐구하였다.
결론적으로, 동적계획법은 단순히 특정 유형의 문제를 푸는 코딩 기술에 머무르지 않는다. 그것은 복잡하고 거대한 문제를 체계적으로 분해하고, 상태와 전이 관계를 통해 모델링하며, 점진적으로 최적해를 구축해 나가는 강력하고 보편적인 ‘사유의 틀(Framework of Thought)’이다. 알고리즘 설계에 있어 이러한 동적계획법적 사고방식은 여전히 모든 문제 해결의 근간을 이룬다.
더 나아가, 동적계획법이 제시한 이론적 토대와 그 한계를 극복하려는 지적 투쟁의 과정은 현대 인공지능, 특히 강화학습의 발전에 결정적인 자양분이 되었다. 동적계획법이 던진 질문에 답하기 위한 노력이 오늘날의 인공지능 기술을 이끌었다는 점에서, 그 학문적 가치와 현대적 의의는 시간이 지날수록 더욱 깊어지고 있다. 따라서 동적계획법에 대한 깊이 있는 이해는 과거의 알고리즘을 학습하는 것을 넘어, 미래의 지능 시스템을 설계하고 이해하는 데 필수적인 지적 기반이라 할 수 있다.
| [알고리즘] 동적 계획법(DP)과 탐욕 알고리즘(Greedy)이란? | 6mini.log, 8월 18, 2025에 액세스, https://6mini.github.io/computer%20science/2021/12/04/dp-greedy/ |
| 알고리즘 분석 | Dynamic Programming | 0/1 배낭 문제 Knapsack Problem 쉽게 이해하기, 8월 18, 2025에 액세스, https://jelong.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%EC%84%9D-Dynamic-Programming-01-%EB%B0%B0%EB%82%AD-%EB%AC%B8%EC%A0%9C-Knapsack-Problem-%EC%89%BD%EA%B2%8C-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0 |
| DP ( Dynamic Programming , 동적 계획법 ) | TIL, 8월 18, 2025에 액세스, https://nelmm.gitbook.io/til/algorithm/dynamic-programming |
| Dynamic programming | Bioinformatics Class Notes - Fiveable, 8월 18, 2025에 액세스, https://library.fiveable.me/bioinformatics/unit-3/dynamic-programming/study-guide/IvdtlVyGWuX3q6P0 |
| Applications of dynamic programming | Mathematical Methods for Optimization Class Notes | Fiveable, 8월 18, 2025에 액세스, https://library.fiveable.me/mathematical-methods-for-optimization/unit-18/applications-dynamic-programming/study-guide/frC2mUdyP0eRJ6RK |