최소 행렬 곱셈 연산 순서 알고리즘 (Matrix Multiplication)

행렬의 곱셈을 수행할 때에는 특별한 법칙이 있다.

곱하고자 하는 앞 행렬의 Column 수와 뒷 행렬의 Row 수가 일치해야 하며, 계산 결과로 앞 행렬의 Row X 뒷 행렬의 Column 크기를 갖는 행렬 결과가 나타난다.

그렇기 때문에 여러 개의 행렬을 곱할 때, 행렬의 곱셈 순서에 따라 곱셈 연산의 순서가 달라진다. 

앞 행렬의 Column 과 뒷 행렬의 Row 가 넓은 범위에서 공통될 수록 연산의 비용이 커지게 된다.

행렬의 곱셈은 CS에서도 많이 사용되는 연산이기 때문에 이 문제는 알고리즘적으로도 유명한 행렬 곱셈(Matrix Multiplication) 문제이다.

이 문제의 일반적인 솔루션은 DP를 이용한 방식으로 O(n^3) 만큼의 시간복잡도와 O(n^2)의 공간복잡도를 갖는다.

간단하고 직관적이므로 DP를 입문할 때 대표적인 예제로 많이 언급된다.

각각 r[i]개의 행(row)과 c[i]개의 열(column) 을 가진 행렬 n개를 순차적으로 곱셈한다고 가정해보자.

여기서 순차적이라 함은 가령 (AB)C 와 A(BC) 처럼 A, B, C 행렬 3개의 곱의 순서가 보장되어야 한다는 것이다.

이 때 알고리즘은 다음과 같다.

(정의)

dp[i][j] => 행렬i부터 행렬j 까지를 곱할 때 필요한 곱셈의 최소횟수

dp[i][j] = dp[i][k] + dp[k+1][j] + 곱셈 비용 의 최솟값.

간단히 설명하면 구간 i ~ j까지 행렬곱셈을 수행시, i~k 까지의 행렬곱셈 X k+1~j 까지의 행렬곱셈 을 순차적으로 수행하는데 추가로 k~k+1 두 곱셈 결과 행렬의 연산 비용을 추가해주는 것이다.

다음 예제와 해답 코드로 공부해보도록 하자.

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

#include <iostream>

using namespace std;

int n = 0;

int r[501] = { 0, };

int c[501] = { 0, };

int dp[501][501] = { 0, };

int min(int a, int b)

{

    return (a > b) ? b : a;

}

int main()

{

    cin >> n;

    for (int i = 0; i < 501; i++)

    {

        for (int j = 0; j < 501; j++)

        {

            dp[i][j] = 0xfffffff;

        }

    }

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

        cin >> r[i] >> c[i];

        dp[i][i] = 0;

    }

    int cnt = 0;

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

    {

        for (int j = 0; j+i < n; j++)

        {

            for (int k = 1; j + k < n; k++)

            {

                int left = dp[j][j + k - 1];

                int down = dp[j + k][j + i];

//곱셈 결과

                int val = (c[j + k - 1] == r[j + k]) ? r[j] * c[j + k - 1] * c[j + i] : 0xfffffff;

                dp[j][j + i] = min(dp[j][j + i], left + down + val);

            }

        }

    }

    cout << dp[0][n - 1] << endl;

    return 0;

}

Matrix Multiplication 알고리즘은 Strassen Algorithm 을 통해 O(n^2)에 가깝게 튜닝이 가능하다. 

다소 수학적인 이해가 필요하므로 다음 링크를 참조한다.

(https://en.wikipedia.org/wiki/Matrix_multiplication)