18. matrix multiplication2 [9 2 주차]

18. Matrix Multiplication2 [9-2 주차]

2024년 1월 14일 일요일

오전 1:55

<Matrix Multiplication2>

행렬 A1, A2, …, An의 곱을 구하자.

(각 행렬의 크기는 p0 x p1, p1 x p2, … , pn-1 x pn 이다)

행렬의 곱은 결합 법칙이 성립하므로 연산 순서가 다양하다.

 

Ai * Aj 는 총 pi-1 * pi * pj 번의 스칼라 곱 연산이 필요하다. 이는 행렬을 곱하는 데 드는 비용이다. -> 숫자 pi는 다음 계산에서 없어짐.

안쪽 숫자가 큰 행렬 곱을 먼저 계산하면 큰 숫자가 다시 계산되지 않으므로, 더 빠르게 계산할 수 있다. 행렬의 곱의 최소 비용을 동적 프로그래밍을 통해 구해 보자.

 

Ai … Aj의 괄호를 최적으로 묶었을 때, Ak와 Ak+1에서 나누어진다고 가정한다. (즉, 마지막 곱은 Ai…k * Ak+1…j 가 된다.)

Ai … Aj의 괄호를 최적으로 묶는 경우에서 Ai … Ak의 괄호를 묶는 방법은, Ai … Ak의 괄호를 최적으로 묶는 방법이어야 한다. 만약 그렇지 않다면, Ai … Aj중 Ai … Ak의 괄호를 묶는 방법을 최적으로 대체하면 더 좋은 답이 나와 모순이 발생한다.

마찬가지 이유로, Ai … Aj를 최적으로 묶는 방법에서 Ak+1 … Aj의 괄호를 묶는 방법도 최적이다.

-> 큰 문제의 최적해가 부분 문제의 최적해를 포함. 최적 부분 구조

 

D[i, j]를 행렬 Ai부터 Aj까지를 곱할 때의 최소 비용이라 하면, 다음이 성립한다.

D[i, i] = 0

D[i, j] = D[i, k] + D[k+1, j] + pi-1 * pk * pj  (i < j)

 

문제는 k의 값이 무엇인지를 알 수 없다는 것이다. 따라서 k 가 i일 때, i+1일 때, …, j-1일 때의 답을 모두 구해야 한다. 그중 최소가 되는 값이 진짜 답이다. 이에 따라 다음 점화식을 세울 수 있다.

 

위 k로 나눠지는 경우를 모두 확인하면, 전체 답을 구하는데 지수 시간이 걸린다. 이는 행렬의 괄호를 묶는 모든 경우의 수를 전부 확인하는 방법보다 나을 게 없다.

 

여기서 주의해야 할 점은 부분 문제가 중복되는 경우가 많다는 것이다. 예를 들어, D[1, 10]을 구하는 과정에서 D[1, 3]과 D[1, 4]가 계산되는데, D[1, 4]를 구하는 과정에서 D[1, 3]이 다시 계산된다. 따라서 이차원 배열 D를 생성하고, D[i][j]에 D[i, j]를 저장해 가져다 씀으로써, 재귀 호출이 중복되는 것을 방지하자.

 

다음으로, 재귀 호출 과정에서 값들이 어떤 순서로 계산되는지 파악하자. 맨 처음으로 계산되는 것은 길이가 1인 행렬의 곱, 즉 하나의 행렬에 대한 비용이다. 행렬 하나에 대해서는 곱셈 연산을 할 게 없으므로 비용이 0이다.

for(i = 1 to n)

D[i][i] = 0;

 

다음으로, 길이가 2인 곱이 연산된다.

for(i = 1 to n-1)

D[i][i+1] = pi-1 * pi * pi+1

 

이제 길이가 L인 곱이 연산된다. L은 2부터 n까지 차례대로 연산된다.

for(i = 1 to n-L+1)

j = i+L-1;

D[i][j] =

 

 

전체 코드는 다음과 같다.

 

int M(int p[], int n) {

int D[n+1][n+1];

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

D[i][i] = 0;

 

for (L=2; L<=n; L++) {

for (i=1; i<=n-L+1; i++) {

j = i + L -1;

minival = ∞;

for (k=i; k<=j-1; k++)

minival = min(minival, D[i][k] + D[k+1][j] + (p[i-1] * p[k] * p[j]) );

D[i][j] = minival;

}

}

return D[1][n];

}

 

루프가 세 번 중첩되어 있고, 각 루프 인덱스는 최대 n-1개의 값을 가지므로, 시간복잡도는 O(n³)이다.