[알고리즘] 다이나믹 프로그래밍 (1)

• 특정 알고리즘이 아닙니다, 단지 테크닉한 분류입니다. ( Divide-and-conquer 처럼 )

divide-and-conquer vs dynamic programming

전자는, the problem into disjoint subproblems. 후자는 , subproblems overlap

dynamic programming은 optimization problem에서 가장 효율적인 정답들 중 하나를 찾아내는 것이다.

서로다른 subproblem의 수가 input size 에 polynomial

Four-step method

1. optimal solution을 정의해라.
2. recursively 정의해라.
3. buttom-up 방식으로 그 솔루션을 계산해라.
4. 계산된 정보를 바탕으로 솔루션을 도출해라.

Rod-cutting problem

length:n , price:pi (i = 1,2,..n), revenue rn구해라

자르는 방법의수: 2^n-1

1) optimal pieces: k (1<= k <= n) , 각각 piece 마다 길이 : i1, i2, .. ik( 모두 더하면 n) ,,, rn = pi1+ pi2+ pi3 + ... + pik (각각 피스 마다 최대 )

rn = max(pn, r1 + rn-1, r2 + rn-2 + .. rn-1+r1) : in general 반 나눈거
이때 max 함수 안에 들어있는 각각의 r 은 또다시 각각의 독립적인 막대자르기 문제라고 생각할 수있다.
따라서 전체적 최적해는 각각의 부분구조들의 최적화의 합으로 이용할수 있기에 "optimal substructure"라고 볼 수 있다.

2) 막대 나누기 문제를 보다 쉽게 재귀 구조로 정의하려면
rn = max(1<=i<=n)(pi + rn-i)로 정의할 수 있다. (r0 =0)

3) recurisive top-down implementation

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

근데 이건 같은 인자를 가지고(n-i) 부분에 들어가는 값이 같은값이 중복되어 계속 재귀적으로 호출한다,, 따라서 수행시간은 T(n) = 1+ 시그마 (j=0~ n-1)T(j)
T(n) = 2^n
이건 결국 자르는 방법을 모두 따라가는 것과 동일하기에 이렇게 비효율적인 수행시간이 나오는 것은 당연하다.

4) rod-cutting: dynamic prgramming

time-memory-trading: 중복되는 값을 메모리에 저장해, 나중에 동일한 subproblem이 등장하면 메모리를 참고하여 시간을 절약한다.

exponential -> polynomial 로 엄청난 속도의 절감이 가능하다.

• top-down with memoization
  : array 또는 hash table에 부분문제의 결과를 저장
  if 프로시저 발견, 이 부분문제를 이전에 풀었다 ,,, 저장된 결과를 리턴한다
  else 통상적인 방법으로 이를 계산한다. ,,, memoized 되었다고 말한다.

MEMOIZED_CUT_ROD(p,n)
	let r[0..n] new array
    for i=0 to n
    	r[i] = - infinite
    return MEMOIZED_CUT_ROD_AUX(p,n,r)
    

MEMOIZED_CUT_ROD_AUX(p,n,r)
	if r[n] >= 0
    	return r[n]
   	if n==0
    	q =0
    else q = -infinite
    	for i =1 to n:
    		q = max(q, p[i] + MEMOIZED_CUT_ROD_AUX(p,n-i,r))
   	r[n] = q
    return q

• bottom-up method
  : 작은 사이즈의 subproblem 먼저 풀면, 각 부분문제를 한번만 풀고, 새로 등장하는 부분문제에 필요한 모든 부분 문제들은 이미 풀어둔 상태가 된다.

BOTTOM_UP_CUT_ROD(p,n)
	let r[0..n] let r new array
    r[0] =0
    for j =1 to n
    	q = -infinite
        for i=1 to j
        	q = max(q, p[i] + r[n-i])
        r[j] = q
    return r[n]

둘 모두 O(N^2)

5) Rod cutting : subproblem graph
G(V,E) : dp 의 수행시간 계산에 도움을 줄수도

수행시간은 각각의 subproblem의 수행시간의 합일지도

수행시간dp는, vertice와 edge의 수에 linear 하게 계산이 된다
G(V,E) 는 바로 이 vertice와 edge의 수를 직관적으로 볼수있게 만든 그래프

6) dp는 optimal value (결과) 뿐아니라 choice(과정)도 보여줄 수있다.

PRINT_CUT_ROD_SOLUTION(p,n)
	(r,s) = EXTENDED_BOTTOM_UP_CUT_ROD(p,n)
    while n >0
    	print s{n}
        n = n -s[n]

EXTENDED_BOTTOM_UP_CUT_ROD(p,n)
	let r[0..n] let r new array
    r[0] =0
    for j =1 to n
    	q = -infinite
        for i=1 to j
        	#max에 대한 부분을 직관적으로 조건문으로 풀어서 쓰고 중간에 i 를 잡아 어디서 얼만큼 잘랐는지도 파악함
        	if q< p[i] +r[n-i]
            	q = p[i] + r[n-i]
                s[j] = i
        r[j] = q
    return r[n]

Four-step method :Rod Cutting

1. optimal solution을 정의해라.

   rn -> ri + r(n-i)
   rn -> pi + r(n-i)

2. recursively 정의해라.

   rn = max(pn, r1+rn-1 , ... ,rn-1 + r1)
   rn = max(pi + rn-i)

3. buttom-up 방식으로 그 솔루션을 계산해라.

   EXTENDED_BOTTOM_UP_CUT_ROD(p,n)

4. 계산된 정보를 바탕으로 솔루션을 도출해라.

   PRINT_CUT_ROD_SOLUTION(p,n)