Algorithm] 동적계획법 - 연속 행렬 곱셈

 

 

연속된 행렬들의 곱셈에 필요한 원소 간 최소 곱셈 횟수를 찾는 문제로,

일단 연속된 행렬 간의 곱셈이 모두 가능하다는 전제 조건 하에 이루어진다.

 

A=10X20, B=20X5, C=5X15

 

다음 세 행렬에 대한 계산을 예로 들면, AxBxC는 두 가지 방법으로 계산할 수 있다.

 

1. (AxB)xC

2. Ax(BxC)

 

두 가지 계산은 결과는 아무 차이가 없지만, 순서에 따라서 두 행렬 곱셈의 횟수가 차이가 나기 때문에

이를 최소화하고자 하는 방법을 구성할 필요가 있다.

 

일단, 1번의 계산을 예로 들면, 1번의 계산에서는 AxB는 10x20x5로, 1000회의 원소 곱셈을 시행하고,

AxB 행렬은 10x5로, (AxB)xC는 750회 곱셈을 진행해 전체적으로 1750회의 원소 곱셈을 시행해야 한다.

 

2번의 계산은 BxC는 20x5x15로, 1500회의 원소 곱셈을 시행한 뒤, BxC 행렬은 20x15 행렬이 된다.

Ax(BxC)는 10x20x15는 3000회 곱셈을 진행하므로 4500회의 원소 곱셈이 필요하다.

 

두 행렬의 계산 결과는 동일하지만, 행렬을 계산하는데 있어서 필요한 원소 곱셈의 횟수는 극명하게 차이가 난다. 지금이야 행렬의 크기가 작고 곱셈할 행렬의 수가 적기 때문에 컴퓨터 입장에서는 큰 차이를 보이지 않지만,

행렬의 크기가 커지고 곱셈할 행렬의 수가 커진다면 행렬 곱셈의 순서에 따라서 계산 횟수가 극명하게 차이날 수 있다.

 

이 문제는 동적계획법의 대표적인 문제로, 행렬의 부분 곱셈들을 부분문제라고 생각하고 다음 곱셈을 생각하면 된다.

 

일단 소스코드부터 먼저 보면 DP[j][k]는 j번째 행렬에서부터 k번째 행렬까지의 곱셈 횟수를 나타낸다.

예를 들면 DP[2][5]는 2번째 행렬에서 5번째 행렬까지의 곱셈 횟수를 나타내는 것이다.

그렇다면 우리가 원하고자 하는 결과는 결국 DP[1][n]에 있을 것이다.

소스코드는 아래와 같다.

입력을 받거나 하진 않았고, 구현에만 집중한 코드이니

입력을 받고 싶다면 별도의 입력 과정만 추가하면 된다.

#include <iostream>
using namespace std;
 
int ChainedMatrix(int arr[], int n)
{
    int** DP;
    int i, j, k, L;
    int tmp;
 
    DP = new int*[n];
    for (i = 0; i < n; i++)
    {
        DP[i] = new int[n];
    }
 
    for (i = 1; i < n; i++)
    {
        DP[i][i] = 0;
    }
 
    for (i = 1; i < n; i++)
    {
        for (j = 1; j < n - i; j++)
        {
            k = i + j;
            DP[j][k] = INT32_MAX;
            for (L = j; L <= k - 1; L++)
            {
                tmp = DP[j][L] + DP[L + 1][k] + arr[j - 1] * arr[L] * arr[k];
                if (tmp < DP[j][k])
                {
                    DP[j][k] = tmp;
                    //cout << tmp << endl;
                }
                cout << tmp << endl;
            }
        }
    }
 
    return DP[1][n - 1];
}
 
int main(void)
{
    int arr[] = { 10,20,7,5,30 };
    int n;
    n = sizeof(arr) / sizeof(int);
 
    cout << ChainedMatrix(arr, sizeof(arr) / sizeof(int)) << endl;
}

이제 작동 예시를 한 번 살펴보자.

A1=10x20=a0xa1, A2=20x7=a1xa2, A3=7x5=a2xa3, A4=5x30=a3xa4

DP[1][1], DP[k][k], DP[n][n]은 행렬 곱셈이 없으니 0으로 초기화하고 다음과 같은 과정을 거친다.

 

	1	2	3	4
1	0	1400	INF	INF
2		0	700	INF
3			0	1050
4				0

 

 

알고리즘 수행 과정을 보면 대각선으로 진행한다고 볼 수 있다.

DP[1][2], DP[2][3], DP[3][4]가 채워지는 과정을 설명하는 것보다,

DP[1][3], DP[2][4], DP[1][4]가 구해지는 과정에 대해서 이야기하는 것이 더 중요해

그 부분에 대해서 이야기를 해보겠다.

 

DP[1][3]은 식으로 나타내면 A1xA2xA3를 계산할 때 최소 연산 횟수를 담고 있는 변수지만,

아직 그 값을 알 수 없기 때문에 최대값(소스에서는 INT32의 최대값)으로 초기화하고 구하는 방향으로 설계를 해놓았다.

 

DP[1][3]은 두 가지 값을 구할 수 있다. A1x(A2xA3)를 계산하는 과정과 (A1xA2)xA3를 계산하는 과정으로 두 과정은 L=1, L=2에서 계산되어 적용이 된다.

 

L=1, 1700

	1	2	3	4
1	0	1400	1700	INF
2		0	700	INF
3			0	1050
4				0

L=2, 1750

	1	2	3	4
1	0	1400	1700	INF
2		0	700	INF
3			0	1050
4				0

 

 

DP[2][4]도 이와 동일한 방법으로 구할 수 있고, 그 결과는

L=2, 5250

	1	2	3	4
1	0	1400	1700	INF
2		0	700	5250
3			0	1050
4				0

L=3, 3700

	1	2	3	4
1	0	1400	1700	INF
2		0	700	3700
3			0	1050
4				0

이제 이 문제의 최종해인 DP[1][4]를 구하는 과정인데,

DP[1][4]는 세 가지 경우가 존재한다.

 

A1x(A2xA3xA4), (A1xA2)x(A3xA4), (A1xA2xA3)xA4

이들에 각각 대응하는 경우는

 

L=1, 9700

	1	2	3	4
1	0	1400	1700	9700
2		0	700	3700
3			0	1050
4				0

 

L=2, 4550

	1	2	3	4
1	0	1400	1700	4550
2		0	700	3700
3			0	1050
4				0

 

L=3, 3200

	1	2	3	4
1	0	1400	1700	3200
2		0	700	3700
3			0	1050
4				0

 

 

 

결국 A1xA2xA3xA4를 구하기 위해서 필요한 원소의 최소 곱셈 횟수는 3200회로 계산이 된다.

 

테이블을 작성하는 과정을 봐서 알겠지만, 일단 이 테이블 자체가 n^2 으로 구성되었고 이것의 반만 사용한다.

원소에 대한 계산은 L로 구성된 for문의 연산횟수고 L은 최대 n-1까지 반복하여 수행하기 때문에

O(n^2)xO(n)=O(n^3)의 시간복잡도를 가지고 있다고 볼 수 있다.

 

1차원을 배열을 사용하는 동적계획법의 경우 점화식만 구하면 간단하게 구현할 수 있을 뿐만 아니라,

장하는 값에 대해 신경 쓰는 부분도 그리 많지 않아서 쉽게 구현할 수 있지만,

2차원 배열이 필요한 경우에는 신경 써야 할 부분들이 많아 꽤나 까다롭다.

먼저 연산할 방향, 존재 가능한 경우들을 생각하고 알고리즘을 구성하는 것이 더 쉽게 느껴질 것이다.