Dynamic Programming: 두 판 사이의 차이

2025년 11월 24일 (월) 05:14 기준 최신판

개요

동적 프로그래밍(Dynamic Programming)은 좌우 순서로 배열된 문제들^[1]에 대한 최적화 문제를 효율적으로 푸는 방법이다. 동적 프로그래밍의 핵심적인 아이디어는 복잡한 문제를 작은 하위 문제(subproblem) 로 나누고, 중복 계산을 피하기 위해 이전 결과를 저장(memoization)하는 것이다. 이때 동적 프로그래밍은 재귀적으로 구현한다는 것을 의미하지 않는다. 동적 프로그램의 본질은 어디까지나:

중복되는 하위 문제(Overlapping Subproblems): 예를 들면, 피보나치에서 fib(3)을 여러 번 계산하지 않는 것이 있다.
최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 문제의 최적해들로 구성되는 것이다.

따라서 DP를 구현하는 방식은 아래와 같이 두 가지로 나뉜다:

Top-Down(Memoization): 큰 문제에서 출발해 재귀를 통해 하위 문제를 호출하며, 이미 계산된 값은 저장하여 활용한다.
Bottom-Up(Tabulation): 가장 작은 하위 문제부터 순서대로 반복문으로 해결하며, 결과를 테이블에 저장한다.

동적 프로그래밍은 완전탐색(Exhaustive Search) 방식에 같이 사용된다. 완전 탐색 기법은 모든 가능한 해를 탐색하므로 항상 정답은 구하지만 비효율적이지만 동적프로그램과 같이 응용하여, 중복 계산을 제거하여 효율을 높일 수 있다. 이를 이용한 대표적인 알고리즘으로는 Floyd’s Algorithm이 있다.

Recurrence Relations

점화식(Recurrence Relation)은 어떤 수열을 “이전 항들로 정의하는 식”이다. 즉, "자기 자신을 기반으로 정의된 함수"이다. 예를 들면, 아래와 같은 식이 있다:

 $a_{n} = a_{n - 1} + 1, a_{1} = 1 \Rightarrow a_{n} = n$ 
 $a_{n} = 2 a_{n - 1}, a_{1} = 2 \Rightarrow a_{n} = 2^{n}$ 
 $a_{n} = n a_{n - 1}, a_{1} = 1 \Rightarrow a_{n} = n!$

이와 같이 점화식을 통해 문제의 구조를 반복되는 관계로 표현함으로서 프로그램이 재귀적으로 계산할 수 있다. 즉, 동적 프로그래밍은 이러한 점화식을 효율적으로 계산하기 위해 부분 결과를 저장하는 기법이다.

Master Theorem

이때 점화식은 문제를 작은 하위 문제로 나누었을 때 이를 표현하는 수식이므로, 주어진 점화식을 이용해 알고리즘의 시간복잡도를 추론할 수 있다. 이를 마스터 정리(master theorem)이라고 하며, 이는 분할 정복 알고리즘에도 적용될 수 있다. 마스터 정리는 점화식이 아래와 같은 형태임을 가정한다:

 $T (n) = a \cdot T (n / b) + f (n)$

위에서 a는 분할할 때 문제의 개수, n/b는 분할된 각 문제의 크기, f(n)은 부분 문제의 해를 합치는데 걸리는 비용을 의미한다. 일반화한 이 식을 통해 T(n)의 점근적인 시간복잡도를 구하면 아래와 같다:

Case 1: f(n)=O(nlogba−ϵ), for some ϵ>0
- 즉, 합치는 비용이 부분 문제 비용보다 작다. 이 경우, $T (n) = Θ (n^{l o g_{b} a})$
Case 2: f(n)=Θ(nlogba),
- 즉, 합치는 비용이 부분 문제 비용과 비슷하다. 이 경우, $T (n) = Θ (n^{l o g_{b} a} \cdot l o g (n))$
Case 3: f(n)=Ω(nlogba+ϵ), for some ϵ>0
- 즉, 합치는 비용이 부분 문제 비용보다 크다. 이 경우, $T (n) = Θ (f (n))$
- 단, 정규성 조건이 필요하다: $a \cdot f (n / b) \leq c \cdot f (n)$ for some $c < 1$

Three Steps to Dynamic Programming

마스터 정리를 바탕으로, 동적 프로그래밍을 하기 위한 3단계를 요약하면 아래와 같다:

점화식 세우기: 문제를 작은 하위 문제로 나누고, 이들 결과를 결합하는 수식을 만든다.
서브문제 개수의 다항성 보장: 가능한 하위 문제 수가 너무 많지 않아야 한다.^[2]
계산 순서 결정: 하위 문제의 결과를 이미 계산된 값으로부터 효율적으로 구할 수 있도록 순서를 정한다.

Fibonacci Numbers

피보나치 수열(Fibonacci Numbers)은 동적 프로그래밍의 대표적인 구현 예시 중 하나이다.

피보나치 수열에 대한 자세한 설명은 해당 문서를 참조해주십시오.

Binomial Coefficients

이항 계수(Binomial Coefficients)는 동적 프로그래밍의 고전적인 응용 중 하나이다.

이항 계수(Binomial Coefficients)에 대한 자세한 설명은 해당 문서를 참조해 주십시오.

The Gas Station Problem

The Gas Station Problem에 대한 자세한 설명은 해당 문서를 참조해 주십시오.

Edit Distance

Edit Distance에 대한 자세한 설명은 해당 문서를 참조해 주십시오.

High-Density Bar Codes

바코드 기술이 발달함에 따라, 2D 바코드가 등장했다. 기본적으로 2D 알고리즘을 구현하기 위해서는 문자 타입에 따라 최적 인코딩 방식^[3]을 선택하여 문자열을 인코딩해야 한다. 기존에는 greedy 알고리즘이 사용되어 해당 문자에 가장 좋아 보이는 모드만 선택 방식으로 구현되었다.

PDF-417은 기존 2D 바코드보다 더 밀도있게 정보를 담을 수 있는 2D 바코드이다. PDF-417은 문자를 표현하는 여러 모드(mode)를 가지고 있는데, 문자열 전체를 최적으로 압축하기 위해서 동적 프로그래밍을 사용한다. PDF-417은 문자 타입에 따라 네 가지 모드를 지원하며, Figure 1은 네 가지 모드의 상태 전이도이며, 이는 각 모드를 전환(switch)하기 위해서 필요한 비용을 보여준다. 아래는 상태전이도에 대한 설명이다:

네 가지 모드(state)
1. Alpha (A–Z)
2. Lower Case (a–z)
3. Mixed (0–9, #$% 등)
4. Punctuation (문장부호)
Latch: 한 모드에서 다른 모드로 영구적으로 이동하며, 비용이 크다.(보통 1 코드워드)
Shift: 일시적으로 다른 모드의 한 글자를 표현하는 명령이지만, 비용이 latch보다 작다.

따라서 문장을 인코딩할 때는 “지금 모드를 유지할까? 잠깐 shift할까? latch해서 영구적으로 바꿀까?”라는 복잡한 선택이 필요하다. 기존 방식과 달리 동적 프로그래밍을 활용하면 모든 prefix에 대해 모든 모드의 최소 비용을 계산할 수 있다. 이를 위한 DP 테이블은 M[i][j]와 같이 구성된다. 이는 모드 j에서 끝난 i번째 문자까지 고려했을 때 누적 최소 비용을 의미한다. 이에 대한 DP 점화식은 아래와 같다:

 $M [i] [j] = m i n (M [i - 1] [k] +$ i번째 문자를  $k$ 에서  $j$ 로 인코딩한 비용

이는 단순한 greedy 알고리즘보다 평균 8%이상 성능을 개선하는 효과를 가진다.

Book Partition Problem

책 분할 문제(Book Partition Problem)는 책들의 길이가 다를 때, 이를 k명의 작업자에게 공평하게 나누는 문제이다. 입력과 문제 상황을 구체화하면 아래와 같다:

Input: 책들의 배열  $S = {s_{1}, S_{2}, \dots, s_{n}}$ , 작업자  $k$ 
Problem: Partition  $S$  into  $k$  ranges, so as to minimize the maximum sum over all the ranges.

예를 들어 $k = 3$ 이고 $S = {100, 200, 300, 400, 500, 600, 700, 800, 900}$ 과 같이 주어진다면, 아래와 같이 분할해야 하는 것이다.

100 200 300 400 500 | 600 700 | 800 900

위는 첫 번째 구간의 합은 1500이고, 두 번째 구간의 합은 1300이고, 세 번째 합은 1700이다. 이는 주어진 문자열에 대해 각 구간의 합을 가능한 한 비슷하게 만들어, 가장 큰 구간의 합을 최소화한 것이다. 이때 평균을 기준으로 나누는 방식은 항상 최적을 보장해주지 않기 때문에, 동적 프로그래밍이 해당 문제를 해결하기 위해 사용된다.

점화식을 유도하기 위해, 마지막 partition을 (i+1)~n 구간으로 둔다고 가정하자. 이 경우 마지막 구간의 합은 아래와 같이 구해진다:

 $\sum_{j = i + 1}^{n} s_{j}$

그 이전 구간들(1 ~ i)은 k−1개의 구간으로 나눠져야 한다. 이에 따라 전체 partition의 cost(최대 구간 합)는 아래와 같이 구해진다:

 $M [n, k] = \min_{i = 1}^{n} \max (M [i, k - 1], \sum_{j = i + 1}^{n} s_{j})$ 
base case 1:  $M [1, k] = s_{1}$ : 원소 하나는 구간 합이 그 원소뿐
base case 2:  $M [n, 1] = \sum_{i = 1}^{n} s_{i}$ : 한 구간만 있으면 전체 합

위 점화식을 그대로 구현하면, DP 테이블의 크기는 $n \times k = O (n k)$ 이고, 각 DP cell에 대한 계산은 $1 \leq i \leq n$ 을 만족하는 $i$ 에 대해 전부 계산한다. 이에 따라 총 시간복잡도는 $O (n k) \times O (n) = O (k n^{2})$ 이다.

Limitations of Dynamic Programming

동적 프로그래밍은 효율적이지만 항상 사용 가능한 것은 아니다. 동적 프로그래밍은 부분 문제의 결과를 테이블에 저장하여 전체 계산을 빠르게 하므로, 이를 효율적으로 구현하기 위해서는 부분 문제의 수가 작아야 한다. 예를 들어 순열(Permutations) 문제에 대해, n개의 원소를 순열로 나누면 n!개의 순열이 존재하므로 부분 문제의 수가 많아 이를 다 저장할 수 없다. 따라서 순열 기반 문제는 보통 동적 프로그래밍이 불가능하다. 이는 부분집합의 경우에도 n개의 원소를 가지는 집합에 대한 부분집합의 개수는 2ⁿ이므로 동적 프로그래밍이 불가능하다. 또한 TSP 문제도 동적 프로그래밍으로 기존 $O (n^{2})$ 알고리즘보다 더욱 효율적으로 구현할 수 있음에도 저장의 문제로 구현하지 못하는 예시이다. TSP의 점화식은 아래와 같다:

 $T (i; S) = \min_{j \in S} C [i, j] + T (j; S - {j})$

이 경우 시간복잡도는 $n^{2} 2^{n}$ 이며, 기존 알고리즘보다 더욱 빠르지만 부분문제의 개수가 너무 많아 동적 프로그래밍으로 구현할 수 없다. 반대로 동적 프로그래밍이 적용될 수 있는 대표적인 예시가 문자열 관련 문제인데, 문자열의 substring의 개수는 $n (n + 1) / 2$ 이므로 충분히 적용할 수 있다.

또한 동적 프로그래밍는 선형 구조나, 왼쪽에서 오른쪽으로의 순서가 있는 구조와 같이 순서가 고정된 구조에서 강하다. 이는 예를 들어 트리 구조 관련된 문제, 문자열의 문자들, 행렬 chain, 다각형 boundary 위의 점들과 관련한 문제가 있다.

동적 프로그래밍이 가능하기 위한 가장 중요한 이론적 조건은 Principle of Optimality이다. 이는 아래와 같다:

어떤 문제의 최적 해가 존재하려면 그 해의 부분구성 요소(sub-solution)도 최적이어야 한다.

즉, 전체 최적해의 앞부분이 최적이 아니라면 전체 최적해가 될 수 없다는 것이다. 이 원리가 깨지면 동적 프로그래밍이 불가능하다. 예를 들어 Dijkstra’s Algorithm는 동적 프로그래밍 기반으로 작동한다. 이때 Dijkstra 알고리즘이 동적 프로그래밍으로 구현될 수 있는 이유는 어떤 노드 x까지의 최단 경로가 그 이전 노드까지의 경로가 최단거리를 포함한다는 원칙이 있기 때문이다. 즉, 이는 Principle of Optimality를 만족한다.

각주

↑ 문자열, 수열 등에 관한 문제이다.
↑ 마스터 정리를 통해 계산했을 때 전체 알고리즘의 시간 복잡도가 $O (n^{2}), O (n^{3})$ 정도이면 적당하다.
↑ 숫자 모드, 대문자 모드, 소문자 모드, 문장부호 모드, 혼합 모드

[1] 문자열, 수열 등에 관한 문제이다.

[2] 마스터 정리를 통해 계산했을 때 전체 알고리즘의 시간 복잡도가 $O (n^{2}), O (n^{3})$ 정도이면 적당하다.

[3] 숫자 모드, 대문자 모드, 소문자 모드, 문장부호 모드, 혼합 모드

[1]

[2]

[3]

@@ 1번째 줄: / 1번째 줄: @@
 [[분류:알고리즘 설계와 분석]]
 [[분류:컴퓨터 공학]]
-상위 문서: [[알고리즘 설계와 분석#문제|알고리즘 설계와 분석]]
+상위 문서: [[알고리즘 설계와 분석#Dynamic Programming|알고리즘 설계와 분석]]
 ==개요==
@@ 20번째 줄: / 20번째 줄: @@
 이와 같이 점화식을 통해 문제의 구조를 반복되는 관계로 표현함으로서 프로그램이 재귀적으로 계산할 수 있다. 즉, 동적 프로그래밍은 이러한 점화식을 효율적으로 계산하기 위해 부분 결과를 저장하는 기법이다.
-==Fibonacci Numbers==
+===Master Theorem===
-해당 문단에서는 동적 프로그래밍 활용의 대표적인 예시들 중의 하나인 피보나치 수열을 통해서 동적 프로그래밍의 구현 방법에 대해 알아보는 것을 목표로 한다.
+이때 점화식은 문제를 작은 하위 문제로 나누었을 때 이를 표현하는 수식이므로, 주어진 점화식을 이용해 알고리즘의 시간복잡도를 추론할 수 있다. 이를 마스터 정리(master theorem)이라고 하며, 이는 [[Sorting Problem#Mergesort#Divide and Conquer|분할 정복 알고리즘]]에도 적용될 수 있다. 마스터 정리는 점화식이 아래와 같은 형태임을 가정한다:
+ <math>T(n) = a\cdot T(n/b)+f(n)</math>
+위에서 a는 분할할 때 문제의 개수, n/b는 분할된 각 문제의 크기, f(n)은 부분 문제의 해를 합치는데 걸리는 비용을 의미한다. 일반화한 이 식을 통해 T(n)의 점근적인 시간복잡도를 구하면 아래와 같다:
+*Case 1: <math>f(n) = O(n^{log_b{a-\epsilon}}),</math> for some <math>\epsilon > 0</math>
+** 즉, 합치는 비용이 부분 문제 비용보다 작다. 이 경우, <math>T(n) = \Theta(n^{log_ba})</math>
+* Case 2: <math>f(n) = \Theta(n^{log_ba}),</math>
+** 즉, 합치는 비용이 부분 문제 비용과 비슷하다. 이 경우, <math>T(n) = \Theta(n^{log_ba}\cdot log(n))</math>
+* Case 3: <math>f(n) = \Omega(n^{log_b{a+\epsilon}}),</math> for some <math>\epsilon > 0</math>
+** 즉, 합치는 비용이 부분 문제 비용보다 크다. 이 경우, <math>T(n) = \Theta(f(n))</math>
+** 단, 정규성 조건이 필요하다: <math>a\cdot f(n/b) \le c\cdot f(n)</math> for some <math>c < 1</math>
-===Intuitive Version===
+===Three Steps to Dynamic Programming===
-피보나치 수열의 점화식 정의는 아래와 같다:
+마스터 정리를 바탕으로, 동적 프로그래밍을 하기 위한 3단계를 요약하면 아래와 같다:
- <math>F_n=F_{n-1}+F_{n-2}, F_0=0, F_1=1</math>
+# 점화식 세우기: 문제를 작은 하위 문제로 나누고, 이들 결과를 결합하는 수식을 만든다.
-이를 구현하기 위한 기본적인 방법은 아래와 같다:
+# 서브문제 개수의 다항성 보장: 가능한 하위 문제 수가 너무 많지 않아야 한다.<ref>마스터 정리를 통해 계산했을 때 전체 알고리즘의 시간 복잡도가 <math>O(n^2), O(n^3)</math> 정도이면 적당하다.</ref>
-<syntaxhighlight lang="c">
+# 계산 순서 결정: 하위 문제의 결과를 이미 계산된 값으로부터 효율적으로 구할 수 있도록 순서를 정한다.
-long fib_r(int n) {
-    if (n == 0) return 0;
-    if (n == 1) return 1;
-    return fib_r(n-1) + fib_r(n-2);
-}
-</syntaxhighlight>
-이는 직관적으로 구현된 동적 프로그래밍이지만, 동일한 값을 반복해서 계산하는 비효율이 있다. Figure 1에서 보이는 바와 같이 fib(6)를 계산하려면 fib(5)와 fib(4)이 필요한데, fib(5) 안에서도 다시 fib(4)을 계산한다. 피보나치 수의 성장 비율은 황금비(<math>\phi</math>)로 수렴하며, 이에 따라 입력이 n일 때 재귀 호출은 <math>n^{1.6}</math>번 정도 발생한다. 즉, 단순 재귀는 계산이 폭발적으로 늘어나 너무 느리다는 결론을 얻을 수 있다.
-===Memoization(Top-Down)===
+==[[Fibonacci Numbers]]==
-Memoization은 계산한 결과를 저장(cache) 해서 다시 계산하지 않게 만드는 기법이다. 이는 아래와 같이 구현된다:
+피보나치 수열(Fibonacci Numbers)은 동적 프로그래밍의 대표적인 구현 예시 중 하나이다.
-<syntaxhighlight lang="c">
-#define MAXN 92
-#define UNKNOWN -1
-long f[MAXN+1];
-long fib_c(int n) {
+[[Fibonacci Numbers|피보나치 수열]]에 대한 자세한 설명은 해당 문서를 참조해주십시오.
-    if (f[n] == UNKNOWN) {
-        f[n] = fib_c(n-1) + fib_c(n-2);
-    }
-    return f[n];
-}
-</syntaxhighlight>
-위 코드에서 f[n] 배열은 캐시 기능을 하며, UNKNOWN 값(-1)은 아직 계산되지 않은 상태를 의미한다. 이를 통해서 한 번 계산한 피보나치 수는 저장하여 중복 계산을 방지한다. 재귀 구조에 저장소를 추가한 형태를 top-down 방식의 동적 프로그래밍이라고 한다. 아래는 위의 코드를 실행하기 위해서 f 배열을 초기화한 뒤 fib_c()를 호출하는 드라이버 함수이다:
-<syntaxhighlight lang="c">
-long fib_c_driver(int n) {
-    int i;
-    f[0] = 0;
-    f[1] = 1;
-    for (i = 2; i <= n; i++) {
-        f[i] = UNKNOWN;
-    }
-    return fib_c(n);
-}
-</syntaxhighlight>
-이는 O(n)의 시간 복잡도를 가지므로, 효율적으로 구현되었다고 할 수 있다.
-===Down-Top Dynamic Programming===
+==[[Binomial Coefficients]]==
-Down-Top 동적 프로그래밍은 가장 작은 하위 문제부터 차근차근 해결하면서, 그 결과를 테이블(table)에 저장하고 큰 문제의 답을 점진적으로 만들어가는 방식이다. 이 방식은 메모리를 더 사용하는 대신, 반복문을 사용하여 속도를 더욱 획기적으로 개선할 수 있다는 장점이 있다. 이는 아래와 같이 구현된다:
+이항 계수(Binomial Coefficients)는 동적 프로그래밍의 고전적인 응용 중 하나이다.
-<syntaxhighlight lang="c">
-long fib_dp(int n) {
-    int i;
-    long f[MAXN+1];
-    f[0] = 0;
-    f[1] = 1;
-    for (i = 2; i <= n; i++) {
-        f[i] = f[i-1] + f[i-2];
-    }
-    return f[n];
-}
-</syntaxhighlight>
-이는 시간 복잡도와 공간 복잡도가 모두 O(n)으로, 매우 효율적으로 구현되었다.
-==Binomial Coefficients==
+[[Binomial Coefficients|이항 계수(Binomial Coefficients)]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.
-이항 계수(Binomial Coefficients)는 동적 프로그래밍의 고전적인 응용 중 하나이다. 이항 계수는 수학적으로 아래와 같이 정의된다:
- <math>\dbinom{n}{k}=</math> "n개 중에서 k개를 선택하는 방법의 수"
-이항 계수는 흔히 조합(combination)이라고 불리며, 다양한 분야에 활용된다. 예를 들어 n명의 사람 중 k명을 뽑는 경우의 수이나, n<math>\times</math>m 격자의 왼쪽 위에서 오른쪽 아래까지, 오른쪽 또는 아래로만 이동할 수 있을 때 가능한 경로의 수<ref><math>\dbinom{n+m}{n}</math>이다.</ref>를 구할 때 사용된다. 이 외에도 경로 문제, 선택 문제, 확률 계산 등 매우 다양한 문제에 등장한다.
-이항 계수는 동적 프로그래밍의 전형적인 예시 중 하나이다. 왜냐하면 이항 계수는 반복되는 하위 문제 구조를 갖고 있기 때문이다. 이항 계수는 아래와 같이 계산된다:
+==[[The Gas Station Problem]]==
- <math>\dbinom{n}{k}=\frac{n!}{(n-k)!k!}</math>
+[[The Gas Station Problem]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.
-즉, 팩토리얼을 이용하여 직접 계산할 수 있다. 하지만 이는 중간 계산에서 오버플로(overflow)가 발생한 우려가 있다. 예를 들어, <math>20! = 2,432,902,008,176,640,000</math>이므로 중간 계산이 너무 커져서 자료형이 감당하지 못한다. 따라서 직접 팩토리얼 계산보다는 점화식을 이용하는 방법이 더 안전하고 효율적이다.
-===Pascal’s Triangle===
+==[[Edit Distance]]==
-파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:
+[[Edit Distance]]에 대한 자세한 설명은 해당 문서를 참조해 주십시오.
- <math>>\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}</math>
-바로 위 식의 파스칼의 점화식이다. 이를 직관적으로 표현하면, n번째 원소를 포함하는 경우의 수 <math>\dbinom{n}{k-1}</math><ref>이미 n을 포함하므로, k-1개만 더 선택하면 된다.</ref>와 n번째 원소를 포함하지 않는 경우의 수 <math>\dbinom{n}{k-1}</math><ref>이미 n을 포함하므로, k-1개만 더 선택하면 된다.</ref>를 합치면 n개의 원소 중에서 k개를 선택하는 경우의 수가 된다는 것이다. 이 방식의 장점은 팩토리얼 계산이 필요 없으며, 단순 덧셈 연산으로 해결 가능하므로 동적 프로그래밍 적용에 매우 적합하다는 것이다.
-이를 활용하여, 이항 관계에 대한 기저 조건(base case)을 분석하면 아래와 같다:
+==High-Density Bar Codes==
-# <math>\dbinom{n}{0}=1</math>: 아무 것도 고르지 않는 경우는 항상 1가지 (공집합)
+바코드 기술이 발달함에 따라, 2D 바코드가 등장했다. 기본적으로 2D 알고리즘을 구현하기 위해서는 문자 타입에 따라 최적 인코딩 방식<ref>숫자 모드, 대문자 모드, 소문자 모드, 문장부호 모드, 혼합 모드</ref>을 선택하여 문자열을 인코딩해야 한다. 기존에는 greedy 알고리즘이 사용되어 해당 문자에 가장 좋아 보이는 모드만 선택 방식으로 구현되었다.
-# <math>\dbinom{n}{n}=1</math>: 모든 원소를 고르는 경우도 항상 1가지 (전체 집합)
-즉, 이항 계수에 대한 점화식은 아래와 같이 구해진다:
+PDF-417은 기존 2D 바코드보다 더 밀도있게 정보를 담을 수 있는 2D 바코드이다. PDF-417은 문자를 표현하는 여러 모드(mode)를 가지고 있는데, 문자열 전체를 최적으로 압축하기 위해서 동적 프로그래밍을 사용한다. PDF-417은 문자 타입에 따라 네 가지 모드를 지원하며, Figure 1은 네 가지 모드의 상태 전이도이며, 이는 각 모드를 전환(switch)하기 위해서 필요한 비용을 보여준다. 아래는 상태전이도에 대한 설명이다:
-  <math>\dbinom{n}{k}=
+* 네 가지 모드(state)
-\begin{cases}
+*# Alpha (A–Z)
-, & if k=0 or k=n \\
+*# Lower Case (a–z)
-\dbinom{n-1}{k-1}+\dbinom{n-1}{k}, & otherwise
+*# Mixed (0–9, #$% 등)
-\end{cases}
+*# Punctuation (문장부호)
-</math>
+* Latch: 한 모드에서 다른 모드로 영구적으로 이동하며, 비용이 크다.(보통 1 코드워드)
+* Shift: 일시적으로 다른 모드의 한 글자를 표현하는 명령이지만, 비용이 latch보다 작다.
+따라서 문장을 인코딩할 때는 “지금 모드를 유지할까? 잠깐 shift할까? latch해서 영구적으로 바꿀까?”라는 복잡한 선택이 필요하다. 기존 방식과 달리 동적 프로그래밍을 활용하면 모든 prefix에 대해 모든 모드의 최소 비용을 계산할 수 있다. 이를 위한 DP 테이블은 M[i][j]와 같이 구성된다. 이는 모드 j에서 끝난 i번째 문자까지 고려했을 때 누적 최소 비용을 의미한다. 이에 대한 DP 점화식은 아래와 같다:
+  <math>M[i][j] = min(M[i-1][k]+</math>i번째 문자를 <math>k</math>에서 <math>j</math>로 인코딩한 비용
+이는 단순한 greedy 알고리즘보다 평균 8%이상 성능을 개선하는 효과를 가진다.
-===Binomial Coefficients Implementation===
+==Book Partition Problem==
-아래는 위의 점화식을 C코드로 표현한 것이다:
+책 분할 문제(Book Partition Problem)는 책들의 길이가 다를 때, 이를 k명의 작업자에게 공평하게 나누는 문제이다. 입력과 문제 상황을 구체화하면 아래와 같다:
-<syntaxhighlight lang="c">
+ Input: 책들의 배열 <math>S=\{s_1,S_2,\cdots,s_n\}</math>, 작업자 <math>k</math>
-long binomial_coefficient(int n, int k) {
+ Problem: Partition <math>S</math> into <math>k</math> ranges, so as to minimize the maximum sum over all the ranges.
-    int i, j;
+예를 들어 <math>k = 3</math>이고 <math>S = \{100, 200, 300, 400, 500, 600, 700, 800, 900\}</math>과 같이 주어진다면, 아래와 같이 분할해야 하는 것이다.
-    long bc[MAXN+1][MAXN+1];
+200 300 400 500 | 600 700 | 800 900
+위는 첫 번째 구간의 합은 1500이고, 두 번째 구간의 합은 1300이고, 세 번째 합은 1700이다. 이는 주어진 문자열에 대해 각 구간의 합을 가능한 한 비슷하게 만들어, 가장 큰 구간의 합을 최소화한 것이다. 이때 평균을 기준으로 나누는 방식은 항상 최적을 보장해주지 않기 때문에, 동적 프로그래밍이 해당 문제를 해결하기 위해 사용된다.
-    // base cases
+점화식을 유도하기 위해, 마지막 partition을 (i+1)~n 구간으로 둔다고 가정하자. 이 경우 마지막 구간의 합은 아래와 같이 구해진다:
-    for (i = 0; i <= n; i++)
+ <math>\sum^n_{j=i+1}s_j</math>
-        bc[i][0] = 1;
+그 이전 구간들(1 ~ i)은 k−1개의 구간으로 나눠져야 한다. 이에 따라 전체 partition의 cost(최대 구간 합)는 아래와 같이 구해진다:
-    for (j = 0; j <= n; j++)
+ <math>M[n,k]=\min^n_{i=1} \max(M[i,k-1], \sum^n_{j=i+1}s_j)</math>
-        bc[j][j] = 1;
+ base case 1: <math>M[1,k]=s_1</math>: 원소 하나는 구간 합이 그 원소뿐
+ base case 2: <math>M[n,1]=\sum^n_{i=1}s_i</math>: 한 구간만 있으면 전체 합
+위 점화식을 그대로 구현하면, DP 테이블의 크기는 <math>n\times k=O(nk)</math>이고, 각 DP cell에 대한 계산은 <math>1\le i \le n</math>을 만족하는 <math>i</math>에 대해 전부 계산한다. 이에 따라 총 시간복잡도는 <math>O(nk)\times O(n)= O(kn^2)</math>이다.
-    // fill DP table using Pascal’s recurrence
+==Limitations of Dynamic Programming==
-    for (i = 2; i <= n; i++) {
+동적 프로그래밍은 효율적이지만 항상 사용 가능한 것은 아니다. 동적 프로그래밍은 부분 문제의 결과를 테이블에 저장하여 전체 계산을 빠르게 하므로, 이를 효율적으로 구현하기 위해서는 부분 문제의 수가 작아야 한다. 예를 들어 순열(Permutations) 문제에 대해, n개의 원소를 순열로 나누면 n!개의 순열이 존재하므로 부분 문제의 수가 많아 이를 다 저장할 수 없다. 따라서 순열 기반 문제는 보통 동적 프로그래밍이 불가능하다. 이는 부분집합의 경우에도 n개의 원소를 가지는 집합에 대한 부분집합의 개수는 2<sup>n</sup>이므로 동적 프로그래밍이 불가능하다. 또한 TSP 문제도 동적 프로그래밍으로 기존 <math>O(n^2)</math> 알고리즘보다 더욱 효율적으로 구현할 수 있음에도 저장의 문제로 구현하지 못하는 예시이다. TSP의 점화식은 아래와 같다:
-        for (j = 1; j < i; j++) {
+ <math>T(i;S)=\min_{j\in S}C[i,j]+T(j;S-\{j\})</math>
-            bc[i][j] = bc[i-1][j-1] + bc[i-1][j];
+이 경우 시간복잡도는 <math>n^22^n</math>이며, 기존 알고리즘보다 더욱 빠르지만 부분문제의 개수가 너무 많아 동적 프로그래밍으로 구현할 수 없다. 반대로 동적 프로그래밍이 적용될 수 있는 대표적인 예시가 문자열 관련 문제인데, 문자열의 substring의 개수는 <math>n(n+1)/2</math>이므로 충분히 적용할 수 있다.
-        }
-    }
-    return bc[n][k];
+또한 동적 프로그래밍는 선형 구조나, 왼쪽에서 오른쪽으로의 순서가 있는 구조와 같이 순서가 고정된 구조에서 강하다. 이는 예를 들어 트리 구조 관련된 문제, 문자열의 문자들, 행렬 chain, 다각형 boundary 위의 점들과 관련한 문제가 있다.
-}
-</syntaxhighlight>
+동적 프로그래밍이 가능하기 위한 가장 중요한 이론적 조건은 Principle of Optimality이다. 이는 아래와 같다:
+ 어떤 문제의 최적 해가 존재하려면 그 해의 부분구성 요소(sub-solution)도 최적이어야 한다.
+즉, 전체 최적해의 앞부분이 최적이 아니라면 전체 최적해가 될 수 없다는 것이다. 이 원리가 깨지면 동적 프로그래밍이 불가능하다. 예를 들어 [[Shortest Paths#Dijkstra’s Algorithm|Dijkstra’s Algorithm]]는 동적 프로그래밍 기반으로 작동한다. 이때 Dijkstra 알고리즘이 동적 프로그래밍으로 구현될 수 있는 이유는 어떤 노드 x까지의 최단 경로가 그 이전 노드까지의 경로가 최단거리를 포함한다는 원칙이 있기 때문이다. 즉, 이는 Principle of Optimality를 만족한다.
 ==각주==

익명 사용자

검색

Dynamic Programming: 두 판 사이의 차이

이름공간

더 보기

문서 행위

2025년 11월 24일 (월) 05:14 기준 최신판

목차

개요

Recurrence Relations

Master Theorem

Three Steps to Dynamic Programming

Fibonacci Numbers

Binomial Coefficients

The Gas Station Problem

Edit Distance

High-Density Bar Codes

Book Partition Problem

Limitations of Dynamic Programming

각주

둘러보기

둘러보기

위키 도구

위키 도구

익명 사용자

검색

Dynamic Programming: 두 판 사이의 차이

2025년 11월 24일 (월) 05:14 기준 최신판

개요

Recurrence Relations

Master Theorem

Three Steps to Dynamic Programming

Fibonacci Numbers

Binomial Coefficients

The Gas Station Problem

Edit Distance

High-Density Bar Codes

Book Partition Problem

Limitations of Dynamic Programming

각주

둘러보기

위키 도구

문서 도구

분류 목록