행렬 체인 곱셈(MCM) 알고리즘 – 최소 곱셈 횟수 구하기

행렬 체인 곱셈(Matrix Chain Multiplication)이란?

여러 개의 행렬이 체인 형태로 주어졌을 때, 곱셈 연산 횟수를 최소화하는 최적의 곱셈 순서를 찾는 것이 행렬 체인 곱셈 문제의 목표입니다.

행렬 곱셈은 결합법칙(associative law)이 성립하기 때문에, 네 개의 행렬 A, B, C, D가 있을 경우 A(BCD), (AB)(CD), (ABC)D, A(BC)D 등 다양한 순서로 계산할 수 있습니다. 그러나 어떤 순서로 묶어서 계산하느냐에 따라 필요한 스칼라 곱셈의 총 횟수가 크게 달라집니다. 따라서 우리의 과제는 가장 효율적인 곱셈 순서를 찾는 것입니다.

입력으로는 배열 arr가 주어집니다. 예를 들어 arr[] = {1, 2, 3, 4}라면, 이는 세 개의 행렬이 각각 (1×2), (2×3), (3×4) 크기를 가진다는 의미입니다.

입력 및 출력

입력:
입력 행렬들의 차원 정보 {1, 2, 3, 4}.
즉, 행렬은 {(1 x 2), (2 x 3), (3 x 4)} 입니다.

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

알고리즘

matOrder(array, n)

입력 − 행렬 목록, 목록에 포함된 행렬의 개수

출력 − 필요한 최소 행렬 곱셈 횟수

Begin
   n x n 크기의 테이블 minMul을 정의하고, 모든 값을 0으로 초기화
   for length := 2 to n, do
      for i := 1 to n-length, do
         j := i + length – 1
         minMul[i, j] := 무한대(∞)
         for k := i to j-1, do
            q := minMul[i, k] + minMul[k+1, j] + array[i-1]*array[k]*array[j]
            if q < minMul[i, j], then minMul[i, j] := q
         done
      done
   done
   return minMul[1, n-1]
End

C++ 예제 코드

#include<iostream>
using namespace std;

int matOrder(int array[], int n) {
   int minMul[n][n];       // 필요한 스칼라 곱셈 횟수를 저장하는 테이블

   for (int i=1; i<n; i++)
      minMul[i][i] = 0;      // 행렬 하나만 곱할 때 비용은 0

   for (int length=2; length<n; length++) {      // 체인 길이를 2부터 늘려가며 계산
      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

동작 원리 요약

이 알고리즘은 동적 계획법(Dynamic Programming)을 활용합니다. 작은 구간(부분 체인)의 최소 곱셈 비용을 먼저 구해 테이블에 저장한 뒤, 점점 더 긴 체인으로 확장해 나가며 최종적으로 전체 체인의 최소 비용을 얻습니다. 시간 복잡도는 O(n³), 공간 복잡도는 O(n²)입니다.