C++로 배우는 행렬 사슬 곱셈(MCM): O(N³) 동적 계획법 완벽 정리

행렬 사슬 곱셈(Matrix Chain Multiplication, MCM)은 여러 개의 행렬이 주어졌을 때, 곱셈 연산 횟수를 최소화하는 최적의 곱셈 순서를 찾는 고전적인 동적 계획법(Dynamic Programming) 문제입니다.

문제의 핵심: 결합 법칙과 곱셈 순서

행렬 곱셈은 결합 법칙(associative law)이 성립합니다. 즉, 네 개의 행렬 A, B, C, D가 있을 때 A(BCD), (AB)(CD), (ABC)D 등 어떤 방식으로 묶어도 결과 행렬은 같습니다.

하지만 중요한 점은, 묶는 순서에 따라 필요한 스칼라 곱셈 연산 횟수가 크게 달라진다는 것입니다. 따라서 우리의 목표는 가장 효율적인(연산량이 가장 적은) 곱셈 순서를 찾는 것입니다.

입력과 출력 예시

입력으로 배열 arr = {1, 2, 3, 4}가 주어졌다고 가정해 보겠습니다. 이 배열은 다음 세 개의 행렬을 의미합니다.

{(1 x 2), (2 x 3), (3 x 4)}

출력: 이 세 행렬을 곱하는 데 필요한 최소 연산 횟수는 18입니다.

예를 들어 (1×2)(2×3)을 먼저 곱하면 1×2×3 = 6번의 연산이 필요하고, 그 결과(1×3)와 (3×4)를 곱하면 1×3×4 = 12번의 연산이 추가됩니다. 총 6 + 12 = 18번으로, 이것이 최솟값입니다.

알고리즘 설계

이 문제는 부분 문제의 최적해를 이용해 전체 문제의 최적해를 구하는 전형적인 동적 계획법 구조를 가집니다. 2차원 테이블 minMul을 사용하여 각 구간 [i, j]에서의 최소 곱셈 비용을 저장합니다.

matOrder(array, n)
입력: 행렬 목록, 행렬의 개수
출력: 최소 행렬 곱셈 연산 횟수

시작
    n x n 크기의 테이블 minMul을 선언하고 모두 0으로 초기화
    for length := 2 to n-1:
        for i := 1 to n-length:
            j := i + length - 1
            minMul[i, j] := 무한대
            for k := i to j-1:
                q := minMul[i, k] + minMul[k+1, j] + array[i-1] * array[k] * array[j]
                if q < minMul[i, j]:
                    minMul[i, j] := q
    return minMul[1, n-1]
끝

여기서 array[i-1] * array[k] * array[j]는 두 부분 행렬의 곱을 계산할 때 드는 비용을 나타냅니다. 행렬 (i..k)의 결과는 (array[i-1] × array[k]) 크기이고, 행렬 (k+1..j)의 결과는 (array[k] × array[j]) 크기이므로, 두 행렬을 곱하는 데 필요한 스칼라 곱셈 횟수는 세 차원의 곱이 됩니다.

C++ 구현 코드

#include<iostream>
using namespace std;

int matOrder(int array[], int n){
    int minMul[n][n]; // 필요한 스칼라 곱셈 횟수를 저장하는 테이블
    
    // 행렬 하나만 곱하는 경우 비용은 0
    for (int i=1; i<n; i++)
        minMul[i][i] = 0;
    
    // 사슬 길이를 2부터 시작하여 점차 늘려가며 계산
    for (int length=2; length<n; length++){
        for (int i=1; i<n-length+1; i++){
            int j = i+length-1;
            minMul[i][j] = INT_MAX; // 무한대로 초기화
            
            for (int k=i; k<=j-1; k++){
                // 각 분할 지점별 곱셈 비용 계산
                int q = minMul[i][k] + minMul[k+1][j]
                        + array[i-1]*array[k]*array[j];
                if (q < minMul[i][j])
                    minMul[i][j] = q;
            }
        }
    }
    return minMul[1][n-1];
}

int main(){
    int arr[] = {1, 2, 3, 4};
    int size = 4;
    cout << "Minimum number of matrix multiplications: "
         << matOrder(arr, size);
}

실행 결과

Minimum number of matrix multiplications: 18

시간 복잡도 분석

이 알고리즘은 세 겹의 반복문을 사용하므로 시간 복잡도는 O(N³), 공간 복잡도는 2차원 테이블을 사용하므로 O(N²)입니다. 단순히 가능한 모든 순서를 탐색하는 브루트 포스 방식(O(N!) 또는 지수 시간)과 비교하면 매우 효율적이며, 행렬의 개수가 수백 개 수준까지도 실용적으로 처리할 수 있습니다.