# Dynamic Programming[4] - Matrix-Chain Multiplication

# 행렬의 곱셈 : pxq 행렬 A와 qxr 행렬 B 곱하기 = pxr의 행렬 C가 나온다, 행렬은 교환법칙X 결합법칙O이 원칙이다.

* 행렬끼리 곱하려면 첫번째 행렬의 열과 두번째 행렬의 행의 수가 같아야 한다.

#include<stdio.h>
int A[2][3] = { //2행 3열 배열 A
    {1, 2, 3},
    {2, 3, 4}
};
int B[3][2] = { //3행 2열 배열 B
    {1, 2},
    {3, 4},
    {5, 6}
};
int C[2][2] = { 0 }; //결과, 2행 2열 배열 C
void product()
{
    for (int i = 0; i < 2; i++)
    {
        for (int m = 0; m < 2; m++)
        {
            int k = 0;
            for (int j = 0; j < 3; j++)
            {
                C[i][m] += A[i][j] * B[k][m];
                k++;
            }
        }
    }
}
void printC()
{
    for(int i=0 ; i < 2 ;i++)
    {
        for (int j = 0; j < 2; j++)
        {
            printf("%d ", C[i][j]);
        }
        printf("\n");
    }
}
void main()
{
    product();
    printC();
}

=> 계산 횟수 : 2 x 3 x 2

 

# 만약 여러개의 행렬(곱 ABC)을 계산한다면

- 행렬 A는 10x100, B는 100x5, C는 5x50

1) (AB)C : 10x100x5 + 10x5x50 = 7500 번의 곱셈이 필요

2) A(BC) : 100x5x50 + 10x100x50 = 75000 번의 곱셈이 필요

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

 

# Matrix chain multiplication의 optimal substructure (연산량이 가장 적은 계산순서를 구하기)

* i<=j

 

 

 

 

 

#include<stdio.h>
int m[10][10];
 
void initM()
{
    for (int x = 0; x < 10; x++)
    {
        m[x][x] = 0;
        m[0][x] = -1;
    }
    for (int x = 1; x < 10; x++)
    {
        for (int y = 0; y < x; y++)
        {
            m[x][y] = -1;
        }
    }
}
int smallestValueOfM(int i, int j)
{
    int v,smallest = 99999;
 
    for (int k = i; k < j; k++)
    {
        v = (m[i][k] + m[k + 1][j] + (i-1)*k*j);
        
 
        if (v < smallest)
        {
            smallest = v;
        }
    }
 
    return smallest;
}
void product()
{
    for (int n = 2; n < 10 ; n++)
    {
        int r = n;
        for (int i = 1; i <= 10 - n; i++)
        {
            int v = smallestValueOfM(i, r);
            m[i][r] = v;
            printf("i:%d, i:%d = %d \n", i, r, v);
            r++;
        }
        printf("\n \n");
    }
}
void printAll()
{
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            printf("%4d ", m[i][j]);
        }
        printf("\n");
    }
}
void main()
{
    initM();
    product();
    printAll();
}

** 확실하지 않은 코드

 

=> Aij는 p(i-1) x pi 행렬이기에 A1j는 p(0)행입니다. 따라서 A1j는 존재하지 않습니다. (확실하지 않은 코드)