[CLRS] [14-2] Matrix Chain Multiplication

1. Matrix Multiplication (행렬곱)

- 많은 사람들은 알겠지만, 행렬 곱에 대해서 알아가보고 넘어가보자.

- 다음과 같이 행렬 곱을 할 때, (m x k) x (k x n) = (m x n) 꼴로 연산이 되게 된다.

- 여기서 핵심은 k처럼 동일한 숫자가 있어야 한다는 것이다.

- 이를 계산하기위해 3중 for문을 이용한 행렬곱 알고리즘을 이용한다고 생각했을 때 , 연산 횟수는 m*k*n 이된다.

 

 

2. Matrix Chain Multiplication

- 만약 행렬곱이 연속적으로 주어져 있다고 가정하자.

- A*B*C*D

cf) A : 5x4 , B. 4x6, C : 6 x 2 , D : 2x7

- 행렬 곱은 결합법칙이 성립하기 때문에 계산할 수 있는 방법은 다음과 같다.

 

'''

i) (((AB)C)D : 연산횟수 : 5*4*6+5*6*2 + 5*2*7 

ii)((A(BC))D) : 연산횟수 : 4*6*2 + 5*4*2 + 5*2*7

iii) ((AB)(CD)) : 연산횟수 : 5*4*6 + 6*2*7 + 5*6*7

iv) (A((BC)D)) : 연산횟수 : 4*6*2+4*2*7+5*4*7

v) (A(B(CD))) : 연산횟수 : 6*2*7 + 4*6*7 + 5*4*7

'''

- 이러한 5가지 방법중 가장 연산횟수가 작은걸 선택하고자 하는게 이번 문제의 핵심이다.

2.1. Catalan numbers

- 행렬의 개수가 n개이면 연산 하는 가짓수는 C_(n-1) 이 된다.

- 따라서 C(3) = 5가 되기에 5가지 방법이라고 할 수 있다.

 

2.2. DP로 풀어보자.

- 해당 문제를 DP로 풀기위해 공부했던 영상을 공유하고자 한다.(이 영상을 보면서 내가 정리한 내용을 본다면 이해가 수월할 것이다.)

https://www.youtube.com/watch?v=prx1psByp7U

 

2.3. Code(백준)

- 이 문제와 같은 문제가 백준에 업로드되어 있다.

https://www.acmicpc.net/problem/11049

 

- 2.2.에서의 알고리즘을 한번 코드로 구현해보자.

import sys

n = int(sys.stdin.readline())

#d0~dn 까지 저장한 리스트구현 
d = []
for _ in range(n):
    matrix_shape = list(map(int,sys.stdin.readline().split()))
    d.append(matrix_shape[0])
d.append(matrix_shape[1])

#dp matrix 구현
dp_matrix = [[0] * (n+1) for _ in range(n+1)]

#dynamic programming
for dx in range(1,n):
    for i in range(1,n-dx+1):
        j = i+dx
        dp_matrix[i][j] = min([dp_matrix[i][k] + dp_matrix[k+1][j] + d[i-1]*d[k]*d[j] for k in range(i,j)])

print(dp_matrix[1][n])