[알고리즘 정리] 행렬 곱셈 문제 (Matrix Chain Multiplication)

DP: Matrix Chain Multiplication (MCM problem)

Dynamic Programming

다이나믹 프로그래밍은 특정한 알고리즘이라기 보다는 문제를 해결하기위한 전략 중 하나라고 할 수 있다. 언뜻 보면 Divde-and-Conquer랑 비슷해보이지만 둘은 큰 차이가 있다.

Optimization

DP는 문제를 최적화할 수 있는 더 작은 문제를 찾아 점차 큰 문제를 해결하는 방식이다. 만약 어떤 문제의 Solution이 S 라고 한다면, DP는 S보다 작은 문제들의 최선의 Solution을 모두 모아 합친 것이라고 할 수 있다. 따라서, 더 작은 문제를 먼저 해결함으로 큰 문제를 해결하기 때문에, bottom-up 방식이라고 할 수 있다.

Divde-and-Conquer vs. DP

분할 정복 알고리즘은 어떤 문제를 해결하기 위해서 더 작은 문제로 쪼개서 해결하게 되는데, 문제는 이 과정에서 동일한 문제를 여러번 반복해서 해결해야하는 문제가 생기게 된다. 피보나치 수열을 보아도 한번 계산 했던 fib(n-1) 을 다른 경우에서 또 계산하게 될 수도 있다. 하지만 DP는 한 번 계산했던 값들은 미리 table에 저장해두고 다음 계산에서 그 값을 그대로 사용해주기 때문에 불필요한 연산의 반복이 사라진다.

Memoization

DP를 사용하면서, Top-Down approach를 계속 유지하는 방법도 있다. 일반적인 recursion의 문제점은 같은 계산을 불필요하게 반복하는 것이 문제였기 때문에 제일 작은 문제부터 계산했었는데, Memoization 전략을 사용하면 쪼개들어가면서 계산하면서 불필요한 계산문제를 해결할 수 있다. Memoization은 단순하게 테이블을 하나 만들어서 하나의 계산이 끝날때마다 해당 값을 메모해두고 나중에 똑같은 연산이 나오면 테이블에서 값만 꺼내 사용하는 방식이다.

Matrix Chain Multiplication

DP를 통해 해결할 수 있는 유명한 문제를 한번 풀어보자. Matrix Chain Multiplication은 행렬곱셈순서 문제이다. 어떤 다수의 행렬이 있을 때, 괄호를 어디에 위치시키는지에 따라 최종 결과는 같지만 곱셈의 계산량이 달라진다. 왜냐하면, 행렬을 곱하기 위해서는 행렬의 크기가 중요한데, 예를 들어 p x q 행렬을 q x r 행렬과 곱한다면 총 연산 횟수는 p x q x r이 되기 때문이다.

 

더 자세한 예를 살펴보자. 우리에게 세가지 행렬이 있다고 하자. 그리고 각 행렬이 다음과 같은 크기로 정해져 있다고 가정하자.

• A = p X q
• B = q X r
• C = r X s

괄호를 통해 세 행렬의 곱이 가질 수 있는 경우의 수는 총 두가지 이다.

1. (A X B) X C
2. A X (B X C)

1번 상황에 따라 계산한 연산 횟수는 p X q X r + p X r X s = p X r X (q + s) 가 될 것이다.
2번 상황에 따라 계산한 연산 횟수는 q X r X s + p X q X s = (p + r) X q X s 가 된다.

 

지금은 두 가지 경우의 수 밖에 없으니 큰 차이가 없어 보이겠지만, 행렬의 갯수가 늘어남에 따라, 그리고 행렬의 크기에 따라 연산 횟수에는 큰 차이가 있다. 그럼 어떻게 해야 최소한의 연산 횟수로 행렬의 곱을 수행할 수 있을까?

Brute Force

단순하게 모든 경우의 수를 계산하려고 해보자. 행렬의 갯수 N이 2 이상이면, 브루트 포스를 이용한 해결이 걸리는 시간은 결국 모든 경우를 다 확인해봐야 하는데, Ω(2n) 만큼의 시간을 소요하게 된다.

DP

그럼 같은 문제를 다이나믹 프로그래밍으로 풀어보자. 다이나믹 프로그램은 항상 몇개의 단계로 나누어서 접근하면 해결할 수 있다.

Step 1: Find Optimal Substructure

Optimal substructure는 주어진 문제를 해결할 수 있는 더 작은 문제의 처적의 솔루션을 의미한다. 우에게 주어진 행렬의 갯수가 j 개만큼 있다면 우리가 찾을 수 있는 substructure는 AiAi+1Ak 와 Ak+1Ak+2Aj 로 나눌 수 있을 것이다.

 

k는 괄호를 위치시키는 행렬을 의미하고 해당 행렬의 다음 행렬부터 마지막 행렬까지 묶으면 우리가 초기에 가졌던 행렬의 집합을 두 그룹으로 나눌 수 있게 된다.

Step 2: A Recursive Solution

i번째 행렬부터 j까지의 행렬을 곱할 때 필요한 최소한의 곱셈 연산 횟수를 m[i, j] 로 표현해보자. 그렇다면 우리가 구할 최종적인 답은 주어진 j개의 행렬에 대한 최소한의 연산 횟수이기 때문에 m[i, j] 으로 표현할 수 있을 것이다.

 

앞선 Step 1 에서 만들었던 최적의 솔루션에 대한 식을 그대로 사용해보자.

 

시작 행렬 위치인 i 가 주어진 갯수 j 와 같은 값이라면 행렬이 하나뿐 이라는 뜻이기 때문에, 곱셈의 횟수는 0 이 된다. 이것을 식으로 일반화 하면,

 

if i = j, m[i, j] = 0

 

이라고 표현할 수 있다.

 

그렇다면 j 가 i 보다 큰 경우에는 어떨까? Step 1 에서 세웠던 식대로 우리는 행렬들을 두 그룹으로 나누어서 계산을 해보아야 한다. 이 식을 표현하면,

 

if i < j, m[i, j] = m[i, k] + m[k + 1, j] + pi-1pkpj

 

위와 같이 각 그룹의 최소 연산횟수를 구해서 더하고, 두 그룹의 결과로 나온 행렬을 곱할 때 발생하는 총 연산 횟수를 더해주면, 전체 행렬에 대한 최소 연산 횟수를 구할 수 있을 것이다.

Step 3: Computing the optimal costs

괄호를 넣을 수 있는 위치 k 는 i ≤ k < j 임을 기억하면서 최적의 cost 를 찾아보자.

1	2	3	4	5	6
2	0	0	0	0	0
3	x	A	B	C	K
4	x	x	0	0	C
5	x	x	x	0	B
6	x	x	x	x	A

j 가 6이라고 할 때, 즉 주어진 행렬의 길이가 6이라고 할 때 우리는 다음과 같은 m 테이블을 만들 수 있다. 각 칸은 m[i, j], j 를 계산할 때 필요한 최소한의 횟수를 기억하고 있을 것이다.

 

i를 3이라고 하고 전체 길이 6까지 나눌 수 있는 모든 경우의 수를 고려해본다고 하자. k 는 i ≤ k < j 조건을 가지고 있기 때문에, 우리가 고려해야할 경우의 수는 k 가 3일 때, 4일 때, 그리고 5일 때가 될 것이다.

 

앞서 세웠던 recursion equation을 적용해보면,

 

k = 3 일 때, m[3, 6] = m[3, 3] + m[4, 6] + p2p3p6

k = 4 일 때, m[3, 6] = m[3, 4] + m[5, 6] + p2p3p6

k = 5 일 때, m[3, 6] = m[3, 5] + m[6, 6] + p2p3p6

 

세 경우로 표현할 수 있다. 따라서 우리는 세 값중에 최종 연산 횟수가 가장 작은 경우를 선택하면 optimal solution을 구할 수 있게 된다. 주목할 점은, 우리는 m[3, 3] 과 m[6, 6]이 0이라는 것을 이미 알고 있고 테이블에도 기록을 해두었다는 것이다.

 

0으로 초기화된 대각선을 기준으로 그 바로 위에 있는 대각선은 모두 행렬을 두 개만 포함하고 있는 경우일 것이기 때문에 항상 두 행렬의 곱셈 횟수인 pi-1pkpj 에 의해 결정된다. 이런식으로 대각선을 오츨으로 하나씩 이동시켜나가면 모든 경우를 다 다시 계산해볼 필요없이 m[1, j]에 가장 최소 값이 들어가게 될 것이다.

 

이런 방식으로 문제를 풀면, 총 n 개에 대해서 2개의 조합을 뽑아 optimal substructure 를 구성하게 되기 때문에 nC2 + n 으로 경우의 수를 표현할 수 있고, 시간복잡도를 계산하면, Θ(n2) 로 표현할 수 있다.

Step 4: Constructing an Optimal Solution

위 계산을 통해서는 최소한의 연산 횟수만 알아낼 수 있고, k의 위치를 따로 기억하지는 않는다. 그래서 우리는 s[i, j]라는 똑같은 형태의 배열을 만들어서 m 배열에 선택되는 최적의 k값을 기록해줄 것이다.

 

그럼 전체 알고리즘에 대한 pseudo code를 보자

Matrix-Chain-Order (p)
n = legth[p] - 1
for i = 1 to n
    m[i, i] = 0
for r = 2 ro n
    for i = 1 to n - r + 1
        j = i + r - 1
        m[i, j] = infinite
        for k = i to j - 1
            q = m[i, k] + m[k + 1, j] + p[i-1]p[k]p[j]
            if q < m[i, j]
                m[i, j] = q
                s[i, j] = k

위에서 정리한 내용이 직관적으로 보이는 코드이다. MCM 문제가 [백준 알고리즘] 알고리즘에 비슷한 문제로 출제되어 있기 때문에 [백준 알고리즘] 문제를 다음과 같은 코드로 해결해보았다.

문제: https://www.acmicpc.net/problem/11049

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int main()
{
    int N;
    cin >> N;
    int P[502][502];
    int minCost[502][502];

    for (int i = 1; i <= N; i++)
    {
        cin >> P[i][0];
        cin >> P[i][1];
    }

    for (int l = 2; l <= N; l++)
    {
        for (int i = 1; i <= N - l + 1; i++)
        {
            int j = i + l - 1;
            minCost[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++)
            {
                int q = minCost[i][k] + minCost[k + 1][j] + P[i][0] * P[k][1] * P[j][1];
                minCost[i][j] = min(q, minCost[i][j]);
            }
        }
    }
    cout << minCost[1][N];
}

해당 문제에서는 k 값을 따로 기록하지 않아도 최소 연산 횟수만 구하면 되기 때문에 해당 부분은 구현하지 않고 해결했다. 같은 문제를 k값 까지 기록해서 두개의 배열을 모두 출력하도록 만들어 보자.

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int main()
{
    int N;
    cin >> N;
    int P[502][502];
    int minCost[502][502];
    int record[502][502];

    for (int i = 1; i <= N; i++)
    {
        cin >> P[i][0];
        cin >> P[i][1];
    }

    for (int l = 2; l <= N; l++)
    {
        for (int i = 1; i <= N - l + 1; i++)
        {

            int j = i + l - 1;
            minCost[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; k++)
            {
                int q = minCost[i][k] + minCost[k + 1][j] + P[i][0] * P[k][1] * P[j][1];
                if (q < minCost[i][j]){
                    minCost[i][j] = q;
                    record[i][j] = k;
                }
            }
        }
    }

    cout << endl;
    cout << "Minimum multiplication: "<< minCost[1][N] << endl;

    cout << endl;
    cout << "Number of optimal multiplication" << endl;
    for (int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j<=N ; j++){
            cout << minCost[i][j] << "\t";
        }
        cout << endl;
    }

    cout << endl;
    cout << "Paranthesis Position" << endl;
    for (int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j<=N ; j++){
            cout << record[i][j] << "\t";
        }
        cout << endl;
    }

}

배열을 해석할 때는 배열의 인덱스를 괄호로 나눌 위치라고 생각하고 해석하면 된다. 만약 결과의 record 배열에 1행 6열의 값이 3이 나왔다면, 1번째 행렬부터 6번째 행렬까지 행렬에서는 3번 행렬 뒤를 기준으로 1, 2, 3 번째 행렬에 괄호를 치고, 4, 5, 6 번째 행렬에 괄호를 치면 된다.