이 글에서는 행렬들의 배열이 주어졌을 때, 곱셈 연산 횟수를 최소화하는 순서를 찾는 행렬 사슬 곱셈(Matrix Chain Multiplication) C 프로그램을 다룹니다.
행렬 배열은 n개의 요소로 구성되며, 각 행렬의 크기는 arr[i-1] × arr[i] 형태로 정의됩니다. 즉, 인접한 두 요소가 하나의 행렬의 행과 열 개수를 나타냅니다.
문제 이해하기
예시를 통해 문제를 살펴보겠습니다.
입력
array[] = {3, 4, 5, 6}설명
위 배열로 만들어지는 행렬들은 다음과 같습니다.
Mat1 = 3×4, Mat2 = 4×5, Mat3 = 5×6
세 행렬을 곱하는 방법은 두 가지가 있으며, 괄호를 어디에 두느냐에 따라 필요한 곱셈 횟수가 달라집니다.
mat1*(mat2*mat3) → (3×4×6) + (4×5×6) = 72 + 120 = 192회 (mat1*mat2)*mat3 → (3×4×5) + (3×5×6) = 60 + 90 = 150회
두 방식 중 (mat1*mat2)*mat3 순서로 곱할 때 곱셈 횟수가 150회로 가장 적습니다. 이처럼 행렬 사슬 곱셈 문제는 단순히 왼쪽부터 차례로 곱하는 것이 아니라, 최적의 곱셈 순서를 찾아야 하는 것이 핵심입니다.
동적 계획법(Dynamic Programming) 접근
이 문제는 최적 부분 구조(Optimal Substructure)와 중복되는 부분 문제(Overlapping Subproblems)라는 동적 계획법의 두 가지 핵심 성질을 모두 만족하므로, 동적 계획법으로 효율적으로 해결할 수 있습니다.
부분 문제의 결과를 2차원 테이블(minMul)에 저장하고, 구간의 길이를 하나씩 늘려가며 각 구간에서 최소 곱셈 횟수를 계산합니다. 분할 지점 k를 모두 시도해 보면서 가장 작은 값을 선택하는 방식입니다.
동적 계획법을 활용한 C 프로그램
예제 코드
#include <stdio.h>
int MatrixChainMultuplication(int arr[], int n) {
int minMul[n][n];
int j, q;
for (int i = 1; i < n; i++)
minMul[i][i] = 0;
for (int L = 2; L < n; L++) {
for (int i = 1; i < n - L + 1; i++) {
j = i + L - 1;
minMul[i][j] = 99999999;
for (int k = i; k <= j - 1; k++) {
q = minMul[i][k] + minMul[k + 1][j] + arr[i - 1] * arr[k] * arr[j];
if (q < minMul[i][j])
minMul[i][j] = q;
}
}
}
return minMul[1][n - 1];
}
int main(){
int arr[] = {3, 4, 5, 6, 7, 8};
int size = sizeof(arr) / sizeof(arr[0]);
printf("Minimum number of multiplications required for the matrices multiplication is %d ", MatrixChainMultuplication(arr, size));
getchar();
return 0;
}실행 결과
Minimum number of multiplications required for the matrices multiplication is 444
코드 작동 원리
- minMul[i][i] = 0 : 행렬이 하나뿐인 경우 곱셈이 필요 없으므로 비용은 0입니다.
- L(구간 길이) : 2개 행렬부터 시작해 전체 행렬까지 구간을 점진적으로 확장합니다.
- k(분할 지점) : 구간 [i, j]를 k 위치에서 나누어 왼쪽 부분과 오른쪽 부분의 최소 비용에 마지막 두 행렬 뭉치를 곱하는 비용(arr[i-1] × arr[k] × arr[j])을 더합니다.
- 모든 분할 지점을 검사한 뒤 최솟값을 minMul[i][j]에 저장하며, 최종 결과는 minMul[1][n-1]에 담기게 됩니다.
이 알고리즘의 시간 복잡도는 O(n³), 공간 복잡도는 O(n²)입니다. 가능한 모든 곱셈 순서를 일일이 확인하는 완전 탐색(지수 시간)보다 훨씬 효율적이므로, 행렬의 개수가 많아져도 실용적인 성능을 보장합니다.