[Algorithm Part 3] 5. Dynamic Programming algorithms

이번 글에서는, dynamic programming 기법을 활용한 유명 알고리즘에 대해 살펴볼 것이다.

---

1. Chained Matrix Multiplication

다음과 같은 행렬 곱을 생각해보자.

$$\underset{20 \times 2}A \quad \times \underset{2 \times 30}B \quad \times \underset{30 \times 12}C \quad \times \underset{12 \times 8}D$$

어느 순서로 행렬 곱을 하든, 결과는 같다. 하지만 연산 횟수에는 영향을 준다.

$$A(B(CD)) \rightarrow 3680 \\ (AB)(CD) \rightarrow 8880 \\ A((BC)D) \rightarrow 1232 \\ ((AB)C)D \rightarrow 10320 \\ (A(BC))D \rightarrow 3120$$

3번째가 가장 낮은 연산 횟수를 보여주기에, 가장 좋은 연산 순서다.

chained matrix mutliplication은 최적 연산 순서(=최소 연산 횟수의 연산 순서)를 구하는 문제다.

Problem

$\underset{d_0 \times d_1}{A_1} \times \underset{d_1 \times d_2} {A_2} \quad \times \underset{d_2 \times d_3} {A_3} \quad \times \cdots \times \underset{d_{n-1} \times d_n} {A_n}$의 최적 연산 순서

Approach

1. 1. 1. $M[i][j]$ = $A_i A_{i+1} \cdots A_j$의 최소 연산 횟수
         • $M[i][j] = \begin{cases}\underset{i < k < j-1}\min(M[i][k] + M[k+1][j] + d_{i-1} d_k d_j) \\ 0 \quad \mbox{if} \ i = j\end{cases}$
      2. $S[i][j]$ = $A_i A_{i+1} \cdots A_j$의 최적 연산 순서의 최초 분할 지점
         • $S[i][j] = \arg\underset{k}\min(M[i][k] + M[k+1][j] + d_{i-1} d_k d_j) \quad \text{where} \ i < k < j - 1$
   2. M과 S를 대각선에서 (1,n)성분 방향으로 계산 저장합니다.
   3. S으로, P(=최적 연산 순서)을 구합니다.
      • $P[i][j] = \begin{cases}\left(P[i][k]P[k + 1][i]\right) \quad (k = S[i][j]) \\ A_i \quad \mbox{if} \ i = j \end{cases}$

Analysis

base operation: 할당(=assignment) 연산

input size: $n$ (# of matrics)

every-case time complexity:

$$T(n) = \frac{n(n-1)(n+1)}{6} \in \Theta(n^3)$$

---

2. Optimal Binary Search Tree

$$key_1 < key_2 < \cdots < key_n \\ p_1, \ \quad p_2, \ \quad \cdots,\ \quad p_n$$

위와 같이, n개의 key와 각 key의 탐색 확률이 주어졌을 때,

평균 탐색 비용을 최소화할 수 있는 이진 탐색 트리 즉, 최적 이진 탐색 트리를 구하는 문제다.

 

이때, $key_i < key_2 < \cdots < key_j$만 포함한 최적 이진 탐색 트리를 $Tree_{i, j}$라고 하자.

Problem

n개의 key($=key_i$)와 각 key의 탐색 확률($=p_i$)이 주어졌을 때, 최적 이진 탐색 트리(=$Tree_{1, n}$) 구하기

Approach

1. 1. 1. $M[i][j]$ = $Tree_{i, j}$의 평균 탐색 비용
         
         • $M[i][j] = \begin{cases}\underset{i \le k \le j}\min(M[i][k-1] + M[k+1][j]) + \sum_{m=i}^j p_m \quad \text{where} \ i < j \\ p_i \quad \mbox{if} \ i = j\end{cases}$
      2. $S[i][j]$ = $Tree_{i, j}$의 root 노드
         
         • $R[i][j] = \arg\underset{k}\min(M[i][k-1] + M[k+1][j]) \quad \text{where} \ i < j$
   2. M과 S를 대각선에서 (1,n)성분 방향으로 계산 저장한다.
   3. S으로, P(=$Tree_{1, n}$)을 구한다.
      • $P[i][j] = \text{root} = k, \ \text{left tree} = P[i][k-1], \ \text{right tree} = P[k + 1][j] \ (k = S[i][j])$

Analysis

base operation: 할당(=assignment) 연산

input size: $n$ (the # of matrics)

every-case time complexity:

$$T(n) = \frac{n(n-1)(n+4)}{6} \in \Theta(n^3)$$