Dynamic Programming이란?

• 최적화 기법, 복잡한 문제를 작은 문제로 나누어 푸는 것
• Divide & Conquer는 분할된 작은 문제들이 서로 겹치지X
• Dynamic Programming은 서로 겹침
• Naive 하게는 지수함수 시간이 나오지만, 여러 기법으로 $O(n^2), O(n^3)$을 줄일 수 있다.

막대 자르기 문제

강철 막대를 길이에 따라 다르게 가격을 매겨서 팔려고 한다. 길이에 대한 가격은 다음과 같다. 길이가 n인 막대를 어떻게 잘라야 최대 이익으로 팔 수 있을까?

• 자연수 n이 주어져있을 때, $p_{i_1}+p_{i_2}+p_{i_3}+ \cdots +p_{i_k}$ 가 최대가 되게 하기 위한 $i_1 + i_2+ \cdots + i_k=n$ 을 만족하는 자연수 k와 $i_1, i_2, \cdots , i_k$ 찾기

• n=4 일 때,

  1+1+1+1 → p = 2, 1+1+2 → p=7, 1+3 → p=9, 2+2 → p=10

  4 → p=9

  $\therefore$ 2+2 가 가장 좋음

• 방법1 : 각 n에 대하여 모든 경우를 다 조사한다 : 길이가 n일 때 모든 경우의 가짓수는 $2^{n-1}$가지. 수행시간 $\Omega(2^n)$

  이유 : 길이 1씩 되는 지점에 금을 긋고(금 n-1개) 각 금마다 자르거나 자르지 않거나 2가지 결정 가능

• 방법2 : 한쪽 끝에 한 덩이를 자르고 나머지 부분을 최대 이익으로 자른다. 그 후 처음 자른 덩어리 크기에 따라 비교, 이익이 최대인 것을 고른다.

  • $r_n = max\{p_n, p_1+r_{n-1}, p_2+r_{n-2}, \cdots, p_{n-1}+r_1\}$

  • 알고리즘

    

  • 수행시간

    <aside> ⌨️ $T(n) = \Theta(1) + \sum_{i=1}^{n-1}T(i)$ $T(n+1) = \Theta(1) + \sum_{i=1}^{n}T(i) = \Theta(1) + \sum_{i=1}^{n-1}T(i) + T(n)$ $\therefore T(n+1) = 2T(n)$

    $\therefore T(n) = 2^{n-1}-1 = \Theta(2^n)$

    </aside>

• 방법3 : 하향식 막대 자르기

  

  • 방법2 문제점 : 각 과정에 대해 같은 분석을 반복함 → 각 결과를 메모리에 저장하여 재활용하면 됨!

  • 알고리즘

    

    #include <iostream>
    #define MAX -12345
    using namespace std;
    
    int memorizedCutRodAux(int* p,int n, int* r, int size){
    	int q;
    
    	if(r[n]>= 0) return r[n];
    
    	if(n == 0) q = 0;
    
    	else{
    		q = MAX;
    		for(int i = 1; i<=n; i++){
    			q = max(q, p[i] + memorizedCutRodAux(p, n-i, r, size));
    		}
    	}
    	r[n] = q;
    
    	return r[n];
    }
    
    int memorizedCutRod(int* p, int n, int size){
    	int r[size];
    	for(int i = 0; i<size; i++){
    	  r[i] = MAX;
      	}
    	return memorizedCutRodAux(p, n, r, size);
    }
    
    int main() {
      int n;
      int p[11] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
      int size = sizeof(p)/sizeof(p[0]);
      cin>>n;
      int result = memorizedCutRod(p, n, size);
      cout<< result<<endl;
    }
    

  • 수행시간 분석 : r[1] 까지 도달한 후 r[i]로 돌아오면 r[1]~r[i-1]까지 다 구한 것! → 그 외 다른 노드는 방문X

    

    <aside> ⌨️ $T(n) = 1+2+3+ \cdots + n-1$ $\therefore \Theta(n^2)$

    </aside>

• 방법4 : 상향식 막대 자르기 알고리즘

  1~n-1까지 구해서 n을 구하는 방법

  

  • 수행시간 : $\Theta(n^2)$

#include <iostream>
#include <algorithm>
#define MAX -12345
using namespace std;

int bottomUpCutRod(int* p, int n, int size){
	int r[size];
	r[0] = 0;
	int q;

	for(int j = 1; j<=n; j++){
		q = MAX;
		for(int i = 1; i<=j; i++){
			q = max(q, p[i] + r[j-i]);
		}
		r[j] = q;
	}
	return q;
}

int main() {
  int n;
  int p[11] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
  int size = sizeof(p)/sizeof(p[0]);
  cin>>n;
  int buresult = bottomUpCutRod(p, n, size);
  cout<<buresult<<endl;
}

행렬의 곱셈 문제

n개의 행렬 $A_1, A_2, A_3, \cdots, A_n$ 이 주어져있고, $A_i$ 는 $p_{i-1} \times p_i$ 행렬이다. 모든 행렬을 곱할 때 어떤 순서로 구해야 수행시간이 최소로 걸릴까?

행렬 X,Y 를 곱할 때 (XY)로 표기한다.