여러 개의 행렬을 연속해서 곱할 때는 곱하는 순서(괄호 배치)에 따라 필요한 스칼라 곱셈 횟수가 크게 달라집니다. 이 글에서는 동적 계획법(Dynamic Programming)을 활용해 곱셈 횟수를 최소화하는 최적의 괄호 배치, 즉 최적 괄호화(Optimal Parenthesization)를 구하는 C++ 프로그램을 알고리즘 설명부터 소스 코드, 실행 결과까지 자세히 다룹니다.
행렬 체인 곱셈 문제란?
먼저 왜 곱셈 순서가 중요한지 간단한 예로 살펴보겠습니다. 차원이 10×30, 30×5, 5×60인 세 행렬 A, B, C가 있다고 가정해 봅시다.
- (AB)C 순서: 10×30×5 + 10×5×60 = 1,500 + 3,000 = 4,500회
- A(BC) 순서: 30×5×60 + 10×30×60 = 9,000 + 18,000 = 27,000회
결과는 같지만 연산 횟수는 무려 6배나 차이가 납니다. 행렬 개수가 늘어날수록 가능한 괄호 배치의 수는 지수적으로 폭증하기 때문에 모든 경우를 일일이 확인하는 완전 탐색으로는 감당할 수 없습니다. 이때 동적 계획법을 사용하면 중복되는 부분 문제의 결과를 재활용해 효율적으로 최적해를 구할 수 있습니다.
알고리즘
이 프로그램의 핵심 요소는 다음과 같습니다.
a[i][j]: 행렬 A[i]A[i+1]…A[j](= A[i..j])를 계산하는 데 필요한 최소 스칼라 곱셈 횟수. 단, A[i]의 차원은 p[i-1] × p[i]입니다.a[i][i] = 0: 행렬 하나만 곱하는 경우 비용은 0입니다.L: 계산 대상 행렬 체인(chain)의 길이m: 특정 분할점 k에서의 비용(스칼라 곱셈 횟수)b[i][j]: a[i][j]가 최솟값이 되는 분할 위치 k (실제 괄호 배치를 복원할 때 활용)
체인을 두 부분 A[i..k]와 A[k+1..j]로 나누었을 때의 총비용은 다음 점화식으로 표현됩니다.
a[i][j] = min(a[i][k] + a[k+1][j] + p[i-1] × p[k] × p[j])
이를 의사코드로 정리하면 다음과 같습니다.
시작
행렬의 개수 n과 각 행렬의 차원을 입력받는다.
MatrixChain() 함수로 최소 곱셈 횟수를 구한다.
함수 본문:
for i = 1 to n-1
a[i][i] = 0 으로 초기화
for L = 2 to n-1 // 체인 길이
for i = 1 to n - L + 1
j = i + L - 1
a[i][j] = INT_MAX
for k = i to j - 1 // 분할점 탐색
m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j]
if (m < a[i][j])
a[i][j] = m
b[i][j] = k
return a[1][n - 1]
끝
C++ 전체 소스 코드
아래는 위 알고리즘을 그대로 구현한 C++ 코드입니다.
#include<limits.h>
#include<iostream>
using namespace std;
int MatrixChain(int p[], int n) {
int a[n][n];
int b[n][n];
int i, j, k, L, m;
// 행렬 하나만 곱할 때 비용은 0
for (i = 1; i < n; i++)
a[i][i] = 0;
// L: 체인 길이
for (L = 2; L < n; L++) {
for (i = 1; i <= n - L + 1; i++) {
j = i + L - 1;
a[i][j] = INT_MAX;
// 모든 분할점 k에 대해 최솟값 탐색
for (k = i; k <= j - 1; k++) {
m = a[i][k] + a[k + 1][j] + p[i - 1] * p[k] * p[j];
if (m < a[i][j]) {
a[i][j] = m;
b[i][j] = k;
}
}
}
}
return a[1][n - 1];
}
int main() {
cout << "행렬 개수(n) 입력: ";
int n;
cin >> n;
int a[n];
cout << "차원 값 입력: ";
for (int v = 0; v < n; ++v) {
cin >> a[v];
}
cout << "최소 곱셈 횟수: " << MatrixChain(a, n);
return 0;
}
실행 결과
행렬 개수(n) 입력: 5 차원 값 입력: 2 3 7 6 4 최소 곱셈 횟수: 174
입력된 차원 배열 {2, 3, 7, 6, 4}는 각각 2×3, 3×7, 7×6, 6×4 크기의 네 개 행렬을 의미합니다. 프로그램은 이 네 행렬을 곱하는 데 필요한 최소 곱셈 횟수인 174회를 정확히 계산해 출력합니다.
시간 복잡도와 참고 사항
- 시간 복잡도: 체인 길이(L), 시작점(i), 분할점(k)을 위한 세 겹의 반복문으로 인해 O(n³)입니다.
- 공간 복잡도: 2차원 DP 테이블 두 개(a, b)를 사용하므로 O(n²)입니다.
- 위 코드는 컴파일러 확장 기능인 가변 길이 배열(VLA)을 사용하고 있습니다. 표준 C++ 환경에서는
std::vector<std::vector<int>>로 선언하는 것이 더 안전합니다. - b[i][j]에 저장된 분할 정보를 재귀적으로 추적하면 "(A((BC))D)"와 같은 실제 최적 괄호 배치 문자열도 함께 출력할 수 있습니다.