알고리즘 이론 15강(2). 동적 프로그래밍 예제

 

[동적 프로그래밍 요약]

: 최적화 문제 해결할때 사용하는 방법중 하나

# 동적 프로그래밍 4단계

  1. 최적해의 구조의 특징 찾기

  2. 최적해의 값을 재귀적(탑-다운)으로 정의하기

  3. 최적해의 값을 일반적으로 상향식(바텀-업) 방법으로 계산하기

  4. 계산된 정보들로부터 최적해를 구성하기

 

 

 

[1. 막대 자르기 문제(Rod Cutting Problem)]

길이가 n인 막대기를 최고수익을 얻기위해서 어떻게 잘라야 하는가? 단, 길이 i당 가격은 아래의 표와 같다.

# 길이당 가격 표(위 : 길이, 아래 : 가격)

1	2	3	4	5	6	7	8	9	10
1	5	8	9	10	17	17	20	24	30

 

# 풀이

1. 최적해의 구조 특징 찾기

  - 길이 n이 1인 막대 자르기 : [1] => 최대 수익 1 ([1])

  - 길이 n이 2인 막대 자르기 : [2], [1,1] => 최대 수익 5 ([2])

  - 길이 n이 3인 막대 자르기 : [3], [1,2], [2,1], [1,1,1] => 최대 수익 8 ([3])

  - 길이 n이 4인 막대 자르기 : [4], [1,3], [2,2], [3,1], [1,1,2], [1,2,1], [2,1,1], [1,1,1,1] => 최대 수익 10 ([2,2])

  ...

  : 이때, 길이 n의 최적의 분해 = i1 + i2 + ... + ik 일때 최대 수익 rn = pi1 + pi2 + ... + pik 이다.

  - r1 = 1 (길이 1의 최고 수익 : [1])

  - r2 = 5 (길이 2의 최고 수익 : [2])

  - r3 = 8 (길이 3의 최고 수익 : [3])

  - r4 = 10 (길이 4의 최고 수익 : [2,2])

  - r5 = 13 (길이 5의 최고 수익 : [2,3])

  - r6 = 17 (길이 6의 최고 수익 : [6])

  ...

  - rn = (pn, r1+r(n-1), r2+r(n-2), ... r(n-1)+r1) 으로 일반화 가능.

   : 중요한건, 위에 나오는 r1, r2 ... r(n-1)는 부분막대 부분에서 최고 수익을 내는 경우를 합치는 것을 의미한다.

   : 즉, 부분문제로 나누어 해결하는 구조.

  - rn = max(pi + r(n-i))  (1<=i<=n) 으로 더 간단한 식 유도 가능.

 

2. 최적해의 값을 재귀적으로 정의하기

  : 위에서 일반화된 식 rn = (pn, r1+r(n-1), r2+r(n-2), ... r(n-1)+r1)을 재귀적으로 작성해본다.

CUT-ROD(p,n)   if n==0:     return 0   q = -∞   for i = 1 to n     q = max(q, p[i] + CUT-ROD(p , n-i))   return q

 

3. 최적해의 값을 일반적으로 상향식(바텀-업) 방법으로 계산하기

 : 라곤 했지만, 실제로 두가지 방법이 있다.

 1) 메모라이즈 이용한 재귀적 풀이

MEMORIZED-CUT-ROD(p,n)   r[0...n] 새로운 배열 생성   for i = 0 to n     r[i] = -∞           // 배열 초기화   return MEMORIZED-CUT-ROD-AUX(p,n,r)   MEMORIZED-CUT-ROD-AUX(p,n,r)   if r[n] >= 0     return r[n]   if n == 0  // 기존의 재귀적 방식 풀이     q = 0   else     q = -∞     for i = 1 to n       q = max(q, p[i] + MEMORIZED-CUT-ROD-AUX(p, n-i, r))   r[n] = q   return q

  2) 상향식 버전으로 만들기

BOTTOM-UP-CUT-ROD(p,n)   r[0..n] 새로운 배열   r[0] = 0     // 초기값   for j = 1 to n     q = -∞     for i = 1 to j       q = max(q, p[i] + r[j-i])     r[j] = q   return r[n]

 

4. 계산된 정보들로부터 최적해를 구성하기

  : 위 식을 통해 계산한 ri값을 출력해주는 코드 작성과 좀더 최적화된 상향식 코드

EXTENDED-BOTTOM-UP-CUT-ROD(p,n)   r[0..n]과 s[1..n]은 새로운 배열   r[0] = 0   for j = 1 to n     q = -∞     for i = 1 to j       if q < p[i] + r[j-i]  // 기존에 max 함수 이용해서 최대값 구하던 방식을, IF문으로 바꾸고(더욱 최적화)         q = p[i] + r[j-1]         s[j] = i             // 최적 커팅의 정보를 s배열을 하나 더 만들어 저장한다(기존엔 최적해만 계산)     r[j] = q return r[n]

PRINT-CUT-ROD-SOLUTION(p,n)   (r,s) = EXTENDED-BOTTOM-UP-CUT-ROD(p,n)   while n > 0     s[n] 출력     n = n - s[n]

: r배열은 n에 따른 최적해의 정보를 저장하고 있고, s배열은 잘라야 하는 지점의 정보를 가지고 있다.

 (정보 한개만 있어도 되는 이유는... 부분집합.. 알지?)

 

# 결과 예제

i	0	1	2	3	4	5	6	7
r[i]	0	1	5	8	10	13	17	18
s[i]	0	1	2	3	2	2	6	1

 

 

 

[2. 코인 수집 문제(Coin Collecting Problem)]

: 주어진 표에 있는 동적은 최대만 많이 수집해야 한다.

: 단, 움직임은 아래, 혹은 오른쪽으로만 이동가능하다.

출발				ㅇ
	ㅇ		ㅇ
			ㅇ		ㅇ
		ㅇ			ㅇ
ㅇ				ㅇ	도착

 

#풀이

1. 최적해의 구조 특징 찾기

: F(i,j)가 로봇이 시작지점(1,1)에서 (i,j)까지 가져올수 있는 최대한의 코인 개수라 가정하자. (i : row, j : column)

- 최적해의 구조 일반화 : F(i,j) = max{F(i-1,j), F(i,j-1)} + cij    (cij는 해당 (i,j)위치에 코인이 있으면 1, 없으면 0의 값이다)

- 재귀적인 방법

 

2. 최적해의 값을 재귀적으로 정의하기

  : 생략

 

3. 최적해의 값을 일반적으로 상향식(바텀-업) 방법으로 계산하기

  : 위의 일반화된 식을 이용해 주어진 예시를 풀어보면 아래와 같다.

0	0	0	0	1	1
0	1	1	2	2	2
0	1	1	3	3	4
0	1	2	3	3	5
1	1	2	3	4	5

: 이런 특징을 이용해 상향식으로 코드를 작성할 수 있다.

RobotCoinCollection(C[1..n, 1...m])     // C : 코인 정보가 들어 있는 배열   f[1,1] <- C[1,1];   for j <- 2 to m do     F[i,j] <- F[1,j-1] + C[1,j]   for i <- 2 to n do     F[i,1] <- F[i-1, 1] + C[i,1]     for j <- 2 to m do       F[i,j] <- max(F[i-1, j], F[i, j-1] + C[i, j])   return F[n,m]

 

4. 계산된 정보들로부터 최적해를 구성하기

  : 생략