[알고리즘 4강] 동적 프로그래밍

1. 개념

주어진 문제를 여러 개의 부분 문제로 분할

• 문제의 크기가 작은 부분 문제에 대한 해를 저장해 놓고,
  이를 이용하여 크기가 보다 큰 문제의 해를 상향식으로 만들어가는 설계 기법.

• 부분 문제가 독립적이지 않음
  • 부분 문제를 분할하면 중복/공통된 부분 문제를 포함한다.
  • 중복된 부분 문제를 반복해서 푸는 대신에,
    각 부분 문제를 한 번만 풀고 그 해를 저장해 둔다.

---

2. 적용 단계

a. 문제의 특성을 분석하여 최적해와 부분 문제들의 관계를 분석

b. 주어진 문제의 최적해를 부분 문제들의 최적해를 이용하여 계산하는 점화식 도출

c. 최적해의 값을 상향식으로 계산

• 입력 크기가 작은 부분 문제부터 점화식의 해를 구해 저장한 후,
  저장된 해를 이용하여 입력 크기가 큰 부분 문제의 순서로
  부분 문제의 최적해의 값을 계산

d. 계산 결과로부터 주어진 문제의 최적해 계산

---

3. 동전 문제

• n : 동전의 개수
• C[1...n] : 각 동전의 액면가가 내림차순 정렬

최적해와 부분 문제의 관계 분석

거스름돈 T원, k개의 동전 -> 최적해

• C[i]원 동전 하나 제거
  • 거스름돈: T-C[i]원, k-1개의 동전 -> 부분 문제의 최적해

점화식

$A[T] = min(A[T-C[i] + 1)$

• $1\leq i \leq n$
• T원을 만들기 위한 최소 동전의 개수
• $A[0] =0$, 음수 X에 대하여 $A[x]=\infty$

최적해 값 구하기

• n = 3, C[1..3] = {4, 3, 1}

i	$A[i]$
0	0
1	1
2	2
3	1
4	1
5	2
6	x

$A[6] = min(A[6-4]+1, A[6-3]=1, A[6-1]+1)$
= $min(A[2]+1, A[3]+1, A[5]+1)$
= $2$

• 거스름돈 6원을 주기 위해서는 최소 2개의 동전이 필요하다는 의미.

int Find_Coin_Number(C[], n, T) {
	for(i=1; i < =t, i++){
    	A[i] = 무한대;
        for(j=1; j <= n; j++) {
        	if (i >= C[j]) {
            	if (A[i] > A[i - C[j]] + 1) {
                	A[i] = A[i-C[j]] + 1;
                }
            }
        }
    }
    return A[T];
}

최적해 찾기

A[1...T]를 이용하여 T원을 만드는 최적해 X[1...n] (각 동전의 개수)

• $T = \displaystyle\sum_{i=1}^{n}{C[i]X[i]}$ $\quad$ and $\quad$ $min(\displaystyle\sum_{i=1}^{n}{X[i]})$
  
  
• 각 동전 C[i]에 대하여 A[T-C[i]] + 1이 A[T]이면, C[i]를 포함하는 최적해가 존재

int Find_Optimal_Coin(C[], n, T) {
	R = T; # T원 중 남은 거스름돈
    
    for (i=1;  i <= n; i++) {
    	while(R >= C[i] && A[R] == A[R-C[i]] + 1) {
        	X[i]++;
            R = R - C[i];
        }
    }
    return X[1...n];
}

---