Dynamic Programming(1)

동적 프로그래밍 방법

원리: 문제의 크기가 같은 소문제에 대한 값을 저장해놓고, 이를 이용해 크기가 보다 큰 문제의 값을 점진적으로 만들어가는 상향식(bottom-up) 접근 방법

• 각각의 소문제는 원래 문제와 동일하나 입력의 크기만 줄어든다
• 입력 크기가 아주 작은 단순한 문제가 되면 값을 쉽게 구할 수 있고, 소문제의 해는 다시 사용 가능성이 있으므로 테이블에 저장
• 해당 소문제의 값이 필요할 때마다 테이블에서 결과를 바로 이용

→ 작은 문제들의 값을 저장해놓고, 해를 구하는 상향식 방식

→ 값을 구축하는 테이블을 이용함

→ 주로 최적화 문제(최솟값/최댓값)에 적용

• 동적 프로그래밍 방법을 적용하기 위한 조건

  • 최적성의 원리(principle of optimality)를 반드시 만족

    → 주어진 문제에 대한 최적값은 주어진 문제의 소문제에 대한 최적값으로 구성된다.

• 동적 프로그래밍 방법의 적용 과정

  0) 문제의 특성을 분석, 최적성의 원리가 성립되는지를 확인

  1) 주어진 문제에 대해 최적값을 제공하는 점화식을 도출

  2) 가장 작은 소문제부터 점화식의 해를 구해 테이블에 저장

  3) 테이블에 저장된 소문제의 값을 이용해 점차적으로 큰 상위 문제의 값을 구함

피보나치 수열

f(n) = f(n-1) + f(n-2)

Fibo(n) {
	f[0]=0; f[1]=1;
	for (i=2; i<=n; i++)
		f[i] = f[i-1] + f[i-2];
	return f[n];
}

⇒ O(n)

분할정복 방법을 적용한다면?

• 순환 형태의 알고리즘

    int f(n) {
    	if (n<=0) return 0;
    	if (n==1) return 1;
    	else return (f(n-1) + f(n-2));
    }
  

→ 계산 구조도: 소문제가 독립이 아니므로 중복된 계산이 필요

⇒ 매우 비효율적

연쇄 행렬 곱셈

n개의 행렬(M1, M2, …, Mn)을 연쇄적으로 곱하는 경우(*Mn은 각각의 행렬을 의미)

• 결합법칙이 성립

  → 여러가지 다른 곱셈 순서가 존재

  → 연산에 필요한 곱셈의 횟수가 달라진다.

따라서,

• n개의 행렬을 연쇄적으로 곱할 때 최적의 곱셈순서를 구하는 것
  • 최적의 곱셈 순서 → 최소의 기본 곱셈 횟수를 갖는 행렬의 곱셈 순서

예를 들어, 아래와 같은 행렬을 곱해야 한다면,

M1: 30×5 M2: 5×20 M3: 20×15 M4: 15×10

아래와 같은 경우의 수가 나온다.

1) ((M1M2)M3)M4 → 16, 500 2) M1(M2(M3M4)) → 5,500 3) M1((M2M3)M4) → 3,750 4) (M1(M2M3))M4 → 6,900 5) (M1M2)(M3M4) → 12,000

• n개의 행렬을 곱하는 최적의 순서는 n개의 행렬의 어떤 부분집합을 곱하는 최적의 순서를 포함한다.

  즉, 7개의 행렬을 곱하는 최적의 순서가 있다면, : (M1M2)((((M3M4)M5)M6)M7)

  → M3, M4, M5를 곱하는 최적의 순서 ((M3M4)M5) ⇒ 부분문제들의 최적해로 n개의 행렬을 곱하는 최적 순서를 구할 수 있다.

(* 즉 부분문제의 최적이 최적이 아니라면 최적의 값을 구할 수 없음)

⇒ 최적성의 원리를 만족!

• 점화식 도출하기

  n개의 행렬 Mi (di-1×di 차원) (1≤i≤n)

  에 대해서 Mi x Mi+1 x … Mj를 수행하는 데 필요한 곱셈의 최소 횟수를 C(i, j) 라고 한다면,

  구하고자 하는 것은 곧

  → C(1,n) = ?

  j-i=0, 1 .. (n-1)까지 C(i,j)를 차례대로 계산하면 된다.

  → 도출된 일반화된 점화식

  C(i, j) = mini≤k≤j-1 { (Mi...Mk)(Mk+1...Mj) + 결합비용 }

  = min≤k≤j-1 {C(i, k) + C(k+1, j) + di-1dkdj}

• 알고리즘

    MinMatMult (n, d[]) {
    	int i, j, k, s;
    	int C[n+1][n+1];
    	for (i=1; i<=n; i++) C[i][i] = 0; 
    	for (s=1; s<=n-1; s++)
    		for (i=1; i<=n-s; i++) {
    			j = i+s;
    			C[i][j] = mini≤k≤j-1(C[i][k]+C[k+1][j]+d[i-1]d[k]d[j]);
    			P[i][j] = 최소값이 되는 k의 값; 
    		}
    return C[1][n]; 
    }
  

  참조

  입력: 행렬의 개수 n, 행렬의 크기 d[0..n] (i번째 행렬의 크기 d[i-1]xd[i])

  출력: C[1][n] : n개의 행렬을 곱하는 데 필요한 곱셈 횟수의 최소값 P[1..n][1..n] : 최적의 곱셈 순서를 구할 수 있는 배열

값이 테이블에 저장, (대각선 형태로 값이 차례대로 저장 됨)

C(i, i)의 경우는 곱할 값이 없으므로 → 0

n+1씩 추가적으로 저장.

→ 테이블은 총 2개 1)횟수가 저장되는 테이블 2)최적의 순서를 드러내는 갈라지는 지점 index k가 저장되는 테이블

결과적으로는 k의 값을 활용해 그 곱셈순서로 계산하게 된다.

• 성능 분석

...
for (s=1; s<=n-1; s++)
for (i=1; i<=n-s; i++) 
	C[i][j] = mini≤k≤j-1( ... );
...

⇒ O(n3)

(* n = 행렬의 개수)