[Algorithm Part 3] 4. Dynamic Programming

이번 글에서는, divide-and-conquer와 매우 비슷한 기법인 dynamic programming에 대해 살펴볼 것이다.

---

Dynamic Programming

Definition

divide-and-conquer와 개념이 매우 흡사하다.

작은 instance(s)의 solution을 기반으로 original instance의 solution을 푼다.

이때, 작은 instance(s)의 solution(s)을 저장하여, 중복 계산을 방지한다.

Approach

dynamic programming 알고리즘은 다음 2단계 절차를 기반으로 설계돼야 한다.

1. 작은 instance(s)의 solution으로 original instance의 solution을 구하는 재귀 속성($\approx$점화식)을 찾는다.
2. bottom-up 방식으로 문제를 푼다. 즉, lower-level instance(s)를 풀어 저장한 후, upper-level instance(s)를 푼다.

 

이제부터, dynamic programming에 대한 이해도를 높이기 위해, 이 접근법을 활용한 유명 알고리즘에 대해 살펴볼 것이다.

---

1. The Binomial Coefficient

Problem

이항 계수 ${n \choose k}$ 계산

Approach

1. $B[i][j] = \begin{cases} B[i-1][j-1] + B[i-1][j] & 0 < j < i \\ 1 & j = 0 \quad \mbox{or} \quad j = i \end{cases}$
2. $B$의 첫 행부터 n행까지 순차적으로 계산 저장한다.

B의 i번째 행을 구하기 위해선 오직 이전 행만 필요하다.

때문에, 크기가 nk인 2차원 배열 말고, 크기가 k인 1차원 배열을 만들어, 메모리 사용량을 줄일 수 있다.

Analysis

base operation: 할당(=assignment) 연산

input size: n, k

every-case time complexity:

$$\begin{matrix} T(n, k) &=& 1 + 2 + 3 + k + (k + 1) + \cdots + (k + 1) \\ &=& \frac{k(k+1)}{2} + (n - k + 1)(k + 1) = \frac{(2 - k + 2)(k + 1)}{2} \\ &\in& \Theta(nk)\end{matrix}$$

---

2. Floyd's Algorithm for Shortest Paths

최소 경로 문제는 최적화 문제(=optimization problem)다.

최적화 문제의 (optimal) solution은 optimal value를 갖는 모든 candidate solution다.

 

예를 들어, 모든 경로는 candidate solution이며, 경로 길이가 candidate solution의 value다.

가장 낮은 value를 갖은 candidate solution 모두 (optimal) solution이 되며,

(optimal) solution의 value를 optimal value라고 한다. 

---

Problem

최소 경로 찾기 

Approach

1. 1. $P^{(k)}[i][j]$ =  $\{v_1, v_2, \cdots, v_k\}$만으로 구한, $v_i$에서 $v_j$까지 최소 경로
      1. $P^{(0)}[i][j] = [\text{v_i, v_j}], \quad P^{(n)}[i][j] = (\text{shortest path from v_i to v_j})$
      2. $P^{(k)}[i][j] = \begin{cases} P^{(k-1)}[i][j], \quad \mbox{if} \ D^{(k-1)}[i][j] < D^{(k-1)}[i][k] + D^{(k-1)}[k][j]  \\  P^{(k-1)}[i][k] \cup P^{(k-1)}[k][j], \quad \mbox{else} \end{cases}$
   2. $D^{(k)}[i][j]$ = $\{v_1, v_2, \cdots, v_k\}$만으로 구한, $v_i$에서 $v_j$까지 최소 경로 길이
      1. $D^{(0)}[i][j] = W (\text{weight from v_i  to v_j}) \quad D^{(n)}[i][j] = (\text{length of shortest path from v_i to v_j})$
      2. $D^{(k)}[i][j] = \min (D^{(k-1)}[i][j], D^{(k-1)}[i][k] + D^{(k-1)}[k][j])$
   3. $M^{(k)}[i][j]$ = $\{v_1, v_2, \cdots, v_k\}$만으로 구한, $v_i$에서 $v_j$까지 최소 경로의 가장 높은 중간 정점
      1. $M^{(0)}[i][j] = 0 \quad M^{(n)} = (\text{hightest index of mid vertex in shortest path from v_i to v_j})$
      2. $M^{(k)}[i][j] = \begin{cases} M^{(k-1)}[i][j], \quad \mbox{if} \ D^{(k-1)}[i][j] < D^{(k-1)}[i][k] + D^{(k-1)}[k][j]  \\  k, \quad \mbox{else} \end{cases}$
2. $D^{(n)}$와 $M^{(n)}$을 계산 저장한다.
   1. $D^{(0)}$부터 $D^{(n)}$(=optimal value)까지 순차적으로 계산 저장한다.
   2. $M^{(0)}$부터 $M^{(n)}$(=instance(s)간의 관계)$까지 순차적으로 계산 저장한다.              
3. $M^{(n)}$를 통해, 최소 경로$P^{(n)}$(=optimal solution)를 구한다.
   • $P^{(k)}[i][j] = \begin{cases}P^{(k)}[i][k] \cup \{k\} \cup P^{(k)}[k][j], \quad \mbox{if}  \ k \neq 0 \quad (k = M^{(k)}[i][j]) \\ \{i, j\}, \quad \mbox{else}\end{cases}$

Analysis

base operation: 할당(=assignment) 연산

input size: n (=# of vertex)

every-case time complexity:

$$T(n) = n \times n \times n \in \Theta(n^3)$$

---

Dynamic Programming and Optimization Problems

(최적화 문제(=optimization problem)는 optimal value를 갖는 solution을 찾는 문제다.

때문에, optimal solution을 구하기 위해선, 무조건 optimal value를 구해야 한다.)

 

위 예제처럼, dynamic programming을 통해, 최적화 문제를 풀 수 있다.

하지만 모든 최적화 문제를 dynamic programming으로 풀 수 없다.

the principle of optimiality가 적용된 최적화 문제만 풀 수 있다.

upper-level instance의 (optimal) solution 구하기 위해, lower-level instance(s)의 (optimal) solution을 무조건 알아야 하는 경우, the priniciple of optimiality가 적용되었다고 한다.

 

dynamic programming을 통해, 최적화 문제 알고리즘을 설계하기 위해서는, 다음 3단계 절차를 따라야 한다.

1. lower-level instance(s)의 (optimal) solution(s)으로
   upper-level instance의 (optimal) solution을 구하는 재귀 속성($\approx$점화식)을 찾는다.
   
   1. optimal value의 재귀 속성($\approx$점화식)을 찾는다.
   2. optimal value 점화식으로, instance(s)간의 관계식을 찾는다.
2. bottom-up 방식으로, 1). optimal value 계산(=calculate)을 통해, 2). instance(s)간의 관계를 찾고 저장한다.
3. bottom-up 방식으로, optimal solution (by instance(s)간의 관계)을 푼다(=construct) 

---

최적화 문제(=optimization problem)는 optimal value를 갖는 solution을 찾는 문제다.

 

그렇기에, brute-force 기법을 통해 최적화 문제를 풀 수 있다.

즉, 모든 candidate solution을 찾은 후, 2). optimal value를 갖는 solution을 찾는 방식으로 문제를 풀 수 있다.

하지만, candiate solution 경우의 수가 너무 많으면(e.g., $2^n$, $n!$), 매우 비효율적이다.

 

the principle of optimiality가 적용된 최적화 문제라면,

dynamic programming 기법을 이용해, 보다 빠르게 문제를 풀 수 있다.

1). 재귀 속성을 찾은 후, 2). sub-instance(s)의 (optimal) solution만 계산하면 되기 때문이다.

---

다음과 같은 의문이 들 수 있다. "optimal value를 구하는 동시에, optimal solution을 구하면 되지 않을까?"

자세히 말하자면, "instance(s)간의 관계식(1-2) 및 관계(2-2)를 찾지 않고, optimal value를 구하는 동시에 optimal solution을 구하면 되지 않을까?"

물론 그렇게 풀어도 된다. 하지만, 이는 불필요한 sub instance(s)의 (optimal) solution(s)도 계산하게 되는 상황이 나온다.

 

이 상황에 대해 자세히 풀어보겠다.

이항 계수와 같은 일반적인 문제는 instance(s)간의 관계가 고정되어 있다.

즉, 재귀 속성($\approx$ 점화식)에 이미 관계가 나와있다.

때문에, 알고리즘을 설계할 때, original instance(s)와 관련 있는 instance(s)만 풀게 만들었다.

 

반면에, 최적 경로와 같은 최적화 문제는 instance(s)간의 관계가 입력값(=instance)에 따라 변한다.

그렇기 때문에, sub instance(s)의 optimal value를 구하는 동시에 optimal solution을 구하기 되면, 

original instance의 solution와 관련 없는 instance(s)의 solution도 계산할 수도 있다.

 

그렇기에, original instance(s)와 관련 있는 instance(s)가 무엇인지 즉, 관계를 파악한 후,

관련된 instance(s)의 optimal solution만 계산하면 보다 효율적으로 original instance의 solution을 구할 수 있다.