Sanjoy Dasgupta가 저술한 책인 Algorithms을 참고하였다.
1-1. Knapsack(배낭 문제)
일정 가치와 무게가 있는 짐(항목)들을 배낭에 넣을 때, 배낭의 용량을 넘지 않는 선에서 짐들의 가치의 합이 최대가 되도록 짐을 고르는 문제
배낭문제는 반복이 가능한 경우와 반복이 불가능한 경우로 나뉜다.
1-2. Knapsack : 반복이 가능한 경우
$W$ : 가방의 최대 용량
$w_i$ : $i$번째 항목의 무게
$v_i$ : $i$번째 항목의 가치
반복이 가능한 경우는 항목 $i$를 여러번 선택할 수 있는 경우이다.
$K(w)$ : 용량 $W$의 배낭이 달성 가능한 최대 가치일 때, $K(w)$가 항목 $i$를 포함한다고 하자.
이때, 항목 $i$를 제거한다면 $K(w-w_i)$가 된다. 다시 말하자면, $K(w) = K(w-w_i) + v_i$인 것이다. 따라서 최종적으로 $K(w) = \max(K(w-w_i) + v_i)$인 것을 알 수 있다. 이는 곧, 현재 문제를 이전 문제들의 값을 이용해 구할 수 있고, 현재 문제가 이전 문제들로 쪼개진다는 점에서 DP에 최적화된 것을 알 수 있다.
간단히 예를 들어보자.
| 항목 | 무게 | 가치 |
|---|---|---|
| 1 | 6 | 30 |
| 2 | 3 | 14 |
| 3 | 2 | 16 |
| 4 | 1 | 9 |
$K(1) = \max(K(1-w_4) + 9) = 9$
$K(2) = \max((K(2-w_3) + 16),K(2-w_4) + 9)) = 18$
…
이런식으로 구해나가면 된다. 자세한 과정은 생략한다.
시간복잡도는 무게를 1부터 $W$까지 차근차근 대입해가며 $K(W)$를 구해야 하기 때문에 $O(W)$만큼의 시간이 소요되고, 각 무게별로 최대 항목 $n$개 만큼 넣어야하므로 $O(n)$ 시간이 소요된다. 따라서 최종 시간복잡도는 $O(nW)$이다.
1-3. Knapsack : 반복이 불가능한 경우
$K(w, j)$ : 용량이 $w$이고 항목들이 $1, … , j$인 배낭을 이용하여 취할 수 있는 최대 가치
반복이 불가능한 경우의 핵심은 항목 $j$가 최대 가치를 달성하는데 필요한지 아닌지를 판단하는 것이다.
식은 다음과 같다.
$K(w, j) = \max(K(w-w_j, j-1) + v_j, K(w, j-1))$
$K(w-w_j, j-1) + v_j$ : $j$를 포함한 가치 ($n$번째 항목이 $j$일 때)
$K(w, j-1)$ : $j$를 포함하지 않은 가치 ($n$번째 항목이 $j$가 아닐 때)
그리고 다음 과정을 반복한다.
$K(0, j) = 0, K(w, 0) = 0$
for $j = 1$ to $n$ :
for $w = 1$ to $w$ :
if $w_j > W : K(w, j) = K(w, j-1)$
else : $K(w, j) = \max(K(w-w_j, j-1) + v_j, K(w, j-1))$
return $K(w, n)$
위 과정을 통해, $j$가 1부터 $n$까지, $w$가 1부터 $w$까지 for문으로 돌아간다.
따라서 $w_j$가 $W$보다 크면 $K(w, j-1) = K(w, j-1)$이 되는 것이고, 그렇지 않다면 $K(w, j) = \max(K(w-w_j, j-1) + v_j, K(w, j-1))$이 되는 것이다.
최대 시간복잡도는 반복이 가능한 경우와 같은 이유로 $O(nW)$이다.
2-1. Chain matrix multiplication(연쇄행렬곱셈)
두 개 이상의 행렬을 곱할 때 결합법칙에 따라 최소곱셈 횟수를 구하는 문제
예를 들어보자. A가 2x3, B가 3x4, C가 4x5 Matrix라고 한다면 (AB)C는 총 64회, A(BC)는 총 90회의 스칼라 곱 연산을 수행해야 한다. 이처럼 결과는 같은데 수행시간에 차이가 나므로, 행렬의 스칼라 곱 횟수를 미리 가늠해서 전체 계산량을 줄이기 위한 것이 바로 연쇄행렬곱셈 알고리즘이다.
그리고 ABCD = ABC(D) = (AB)C(D) … 처럼 행렬의 곱셈은 부분문제가 서로 겹치므로 DP를 이용하면 효율적으로 계산할 수 있다. 이제 과정을 자세히 알아보자
$M(i, j) : A_i$ x $A_{i+1}$ x … x $A_j$의 최소비용 ($1 \leq i \leq j \leq n$) ($A_i = m_0$ x $m_1$, $m_1$ x $m_2$ x … x $m_{n-1}$ x $m_n$)
이때, $M(i, j)$는 다시 $A_i$ x … x $A_k$와 $A_{k+1}$ x … x $A_j$가 된다.
따라서, $M(i, j) = \min(M(i, k) + M(k+1, j) + m_{i-1}m_km_j)$ ($i \leq k \leq j$)
for $i = 1$ to $n$ : $M(i, j) = 0$
for $S = 1$ to $n-1$ :
for $i = 1$ to $n - S$ :
$j = i + S$
$M(i, j) = \min(M(i, k) + M(k+1, j) + m_{i-1}m_km_j)$
return $M(1, n)$
즉, 전체 행렬을 2개의 부분수열로 분리한 뒤, 최소비용을 구한 후 합쳐주는 것이다. 만약 행렬이 3개라면 $M(1, 2), M(2, 3), M(1, 3)$을 구한 뒤 여기서 최솟값이 답이 된다. 자세한 예시는 생략하겠다.
2-2. Chain matrix multiplication 시간복잡도
위의 과정을 보면 알겠지만 부분문제들은 2차원 표를 구성하고, 각 항목들은 각각 계산하는 데에 $O(n)$시간이 걸린다. 따라서 최종 시간복잡도는 $O(n^3)$이다.