개발 공부 - [동적계획법 (Dynamic Programming)] Dynamic Programming - 4

    

Matrix-Chain Multiplication

행렬의 곱셈

p×q 행렬 A와 q×r 행렬 B 곱하기

void product(int A[][], int B[][], int C[][]) {

     for (int i=0; i<p; i++) {

         for (int j=0; j<r; j++) {

             C[i][j] = 0;

             for (int k=0; k<q; k++)

                 C[i][j] += A[i][k]*B[k][j;]

             }

         }

    }

곱셈연산의 횟수 = pqr

Matrix-Chain 곱하기

- 행렬 A는 10×100, B는 100×5, C는 5×50

- 세 행렬의 곱 ABC는 두 가지 방법으로 계산가능 (결합법칙이 성립)

    (AB를 곱하면 결합법칙이 성립된다)

        (AB)C : 7,500번의 곱셈이 필요 (10×100×5 + 10×5×50)

        A(BC) : 75,000번의 곱셈이 필요 (100×5×50 + 10×100×50)

- 즉 곱하는 순서에 따라서 연산량이 다름

- n개의 행렬의 곱 A1A2A3…An을 계산하는 최적의 순서는?

- 여기서 Ai는 pk-1×pk 행렬이다.

Optimal Substructure

A1 A2 … Ak Ak+1 Ak+2 … An

    X               Y             X는 앞부분의 곱이고

                                   Y는 뒷부분의 곱이다. 

           Z

최종 결과 Z는 직전의 두 행렬 X와 Y의 곱이다.

순환식

m[i, j] AiAi+1 ··· Aj 를 곱하는 최소곱셈 횟수

m[i, j] = 

                        0                                                                             if i = j;

                        mini<_k<_j1(m[i, k] + m[k + 1, j] + pi1pkpj )                     if i < j.

동적계획법

//대각선 중앙은 채우고 시작하기 때문에 n-1 으로 할당

int matrixChain(int n)

{

     for (int i=1; i<=n; i++)

         m[i][i] = 0;

     for (int r=1; r<=n-1; r++) {

         for (int i = 1; i <= n - r; i++) {

             int j = i + r;

             m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];

             for (int k = i+1; k <= j-1; k++) {

                 if (m[i][j] > m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j])

                     m[i][j] = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];

                 }

             }

         }

     return m[1][n];

} 시간복잡도: Θ(n3)

for 문이 3개라서 n^3은 아님... (사실 잘 들어봐도 시간복잡도 잘 따질 줄 모르겠음 --)... )