일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- DATAPATH
- DB
- while
- Linux
- architecture
- php
- for
- html
- instruction
- Pipelining
- function
- data structure
- react
- CSS
- Algorithm
- javascript
- MacOS
- mysql
- github
- Java
- MIPS
- system
- control
- XML
- python
- DS
- Class
- DoM
- web
- computer
- Today
- Total
YYYEJI
[Algorithm] DP로 MCM(Matrix-Chain Multiplication) 풀기 본문
다이나믹 프로그래밍(Dynamic Programming)란?
큰 문제를 작은 문제로 쪼개서 그 답을 리스트에 저장해서 사용하는 알고리즘입니다.
DP를 사용하게 되면 같은 문제를 여러 번 반복되지 않아도 되는 장점이 있기 때문입니다.
Recursion을 사용하면 아래 코드와 같이 자기 자신을 계속 호출하게 됩니다.
Fib(n) {
if(n<2) return n;
else return fib(n-1) + fib(n-2);
}
recursion은 top-down으로 문제를 풀어갑니다.
DP를 사용하면 작은 문제부터 차근차근 해결하면서 같은 문제를 반복하지 않아도 됩니다.
fib(n){
int fib[n+1], i;
fib[0] = 0;
fib[1] = 1;
for(int i = 2; i<n; i++)
fib[i] = fib[i-1]+fib[i-2];
return 0;
}
dp는 bottom-up으로 문제를 풀어나갑니다.
MCM(Matrix-Chain Multiplication)이란?
MCM은 Matrix 곱을 할때 괄호(parenthesis)을 어떻게 묶냐에 따라서
곱셈의 횟수가 달라짐을 이용해 곱셈을 최소한으로 만드는 알고리즘입니다.
A = p x q = 10 x 100 (matrix)
B = q x r = 100 x 5 (matrix)
C = r x s = 5 x 50 (matrix)
A, B, C matrix가 존재할 때 괄호를 두 가지 방법으로 나눌 수 있습니다.
① (AxB)xC
② Ax(BxC)
식을 풀어보면
① (AxB)xC = pxqxr + pxrxs = pxr(q+s) = 10x5(100+50) = 7,500
② Ax(BxC) = qxrxs + pxqxs = (q+r)xqxs = (10+5)x100x50 = 115,000
이 곱셈 횟수가 더 적은 ① 으로 문제를 풀게 됩니다.
다른 예제를 보면
Parenthesizations | solution | Nulber of multiplications |
(A₁(A₂(A₃A₄))), k = 1 | (A₃A₄ = 50*5*30)+(A₂A₃₄ = 10*50*30)+(A₁A₂₃₄=20*10*30) | 28500 |
(A₁((A₂A₃)A₄)) | (A₂A₃ = 10*50*30)+(A₂₃A₄ = 10*5*30)+(A₁A₂₃₄ = 20*10*30) | 10000 |
((A₁A₂)(A₃A₄)), k = 2 | (A₁A₂ = 20*10*50)+(A₃A₄ = 50*5*30)+(A₁₂A₃₄ = 20*50*3) | 47500 |
((A₁(A₂A₃))A₄), k = 3 | (A₂A₃ = 10*50*5)+(A₁A₂₃ = 20*10*5)+(A₁₂₃A₄ = 20*5*30) | 6500 |
(((A₁(A₂)A₃)A₄) | (A₁A₂=20*10*50)+(A₁₂A₃ = 20*50*5)+(A₁₂₃A₄ = 20*50*30) | 18000 |
(k는 괄호를 자른 위치를 의미합니다.)
optimal인 답은 ((A₁(A₂A₃))A₄)됩니다.
DP이용해서 MCM문제 풀기
DP (Dynamic Programming)는 큰 문제를 작은 문제로 분할하여 풀어나가는 최적화 기법입니다.
DP에서 중요한 개념 중 하나는 "optimal substructure" (최적 부분 구조)인데 큰 문제의 최적해가 작은 문제의 최적해들을 활용하여 구할 수 있어야 된다는 개념입니다. 큰 문제를 풀기 위해 작은 문제들의 최적해가 이미 구해져 있어야 된다는 의미입니다.
문제를 풀기 위해 식을 하나 알아야됩니다.
i는 시작하는 Matrix, j는 마지막 matrix, k는 괄호가 잘린 위치입니다.
주어진 matrix입니다.
matrix | dimesion |
A1 | 30(index0) x 35(index1) |
A2 | 35 x 15(index2) |
A3 | 15 x 5(index3) |
A4 | 5 x 10(index4) |
A5 | 10 x 20(index5) |
A6 | 20 x 25(index6) |
p = <30, 35, 15, 5, 10, 20, 25>
아래 표를 bottom-up으로 하나하나 풀어나가면 됩니다.
i \ j | 1 | 2 | 3 | 4 | 5 | 6 |
1 | ||||||
2 | x | |||||
3 | x | x | ||||
4 | x | x | x | |||
5 | x | x | x | x | ||
6 | x | x | x | x | x |
j가 i보다 작은 부분은 풀지 않아도 되기 때문에 x를 쳐줍니다.
if i==j, then m[i,j] = 0 식에 의해 0으로 채워줍니다.
i \ j | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | |||||
2 | x | 0 | ||||
3 | x | x | 0 | |||
4 | x | x | x | 0 | ||
5 | x | x | x | x | 0 | |
6 | x | x | x | x | x | 0 |
아래 공식을 통해 문제를 풀어줍니다.
i \ j | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | ① 15750 | ||||
2 | x | 0 | ② 2625 | |||
3 | x | x | 0 | ③ 750 | ||
4 | x | x | x | 0 | ④ 1000 | |
5 | x | x | x | x | 0 | ⑤ 5000 |
6 | x | x | x | x | x | 0 |
① m[1, 2]
A₁A₂ = 30x35x15 = 15750
② m[2, 3]
A₂A₃ = 35x15x5 = 2625
③ m[3, 4]
A₃A₄ = 15x10x5 = 750
④ m[4, 5]
A₄A₅ = 5x10x30 = 1000
⑤ m[5, 6]
A₅A₅ = 10x20x25=5000
i \ j | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | 15750 | ① 7875 | |||
2 | x | 0 | 2625 | ② 4375 | ||
3 | x | x | 0 | 750 | ③ 2500 | |
4 | x | x | x | 0 | 1000 | ④ 3500 |
5 | x | x | x | x | 0 | 5000 |
6 | x | x | x | x | x | 0 |
① m[1, 3]
A₁(A₂A₃) = m[1,1] + m[2,3] +p₀p₁p₃= 7875
(A₁A₂)A₃ = m[1,2] + m[3,3] = m[1,2] + m[3,3] +p₀p₂p₃ = 18000
② m[2, 4]
A₂(A₃A₄) = m[2,2] + m[3, 4] + p₁p₂p₄= 21750
(A₂A₃)A₄ = m[2,3] + m[4, 4] + p₁p₃p₄= 4375
③ m[3, 5]
A₃(A₄A₅) = m[3,3] + m[4,5] + p₂p₃p₅ = 2500
(A₃A₄)A₅ = m[3,3] + m[4,5] + p₂p₄p₅ = 3750
④ m[4, 6]
A₄(A₅A₆) = m[4,4] + m[5,6] + p₃p₄p₆= 6250
(A₄A₅)A₆ = m[4,5] + m[6,6] + p₃p₅p₆ =3500
i \ j | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | 15750 | 7875 | ① 9375 | ||
2 | x | 0 | 2625 | 4375 | ② 7125 | |
3 | x | x | 0 | 750 | 2500 | ③ 5357 |
4 | x | x | x | 0 | 1000 | 3500 |
5 | x | x | x | x | 0 | 5000 |
6 | x | x | x | x | x | 0 |
① m[1,4]
A₁(A₂A₃A₄) = m[1,1] + m[2,4] + p₀p₁p₄ = 14875
A₁A₂(A₃A₄) = m[1,2] + m[3,4] + p₀p₂p₄ = 21000
A₁A₂A₃(A₄) = m[1,3] + m[4,4] + p₀p₃p₄ = 9375
② m[2,5]
A₂(A₃A₄A₅) = m[2,2] + 2[3,5] + p₁p₂p₅ = 13000
A₂A₃(A₄A₅) = m[2,3] + 2[4,5] + p₁p₃p₅ = 7125
A₂A₃A₄(A₅) = m[2,4] + 2[5,5] + p₁p₄p₅ = 11375
③ m[3,6]
A₃(A₄A₅A₆) = m[3,3] + m[4,6] + p₂p₃p₆ = 5357
A₃A₄(A₅A₆) = m[3,4] + m[5,6] + p₂p₄p₆ = 9520
A₃A₄A₅(A₆) = m[3,5] + m[6,6] + p₂p₅p₆ = 10000
i \ j | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | 15750 | 7875 | 9375 | ① 11876 | |
2 | x | 0 | 2625 | 4375 | 7125 | ② 10500 |
3 | x | x | 0 | 750 | 2500 | 5357 |
4 | x | x | x | 0 | 1000 | 3500 |
5 | x | x | x | x | 0 | 5000 |
6 | x | x | x | x | x | 0 |
① m[1,5]
A₁(A₂A₃A₄A₅) = m[1,1] + m[2,5] + p₀p₁p₅ = 28125
A₁A₂(A₃A₄A₅) = m[1,2] + m[3,5] + p₀p₂p₅ = 27250
A₁A₂A₃(A₄A₅) = m[1,3] + m[4,5] + p₀p₃p₅ = 11875
A₁A₂A₃A₄(A₅) = m[1,4] + m[5,5] + p₀p₄p₅ = 15375
② m[2,6]
A₂(A₃A₄A₅A₆) = m[2,2] + m[3,6] + p₁p₂p₆ = 18482
A₂A₃(A₄A₅A₆) = m[2,3] + m[4,6] + p₁p₃p₆ = 10500
A₂A₃A₄(A₅A₆) = m[2,4] + m[5,6] + p₁p₄p₆ = 18125
A₂A₃A₄A₅(A₆) = m[2,5] + m[6,6] + p₁p₅p₆ = 24625
i \ j | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | 15750 | 7875 | 9375 | 11876 | ① 15125 |
2 | x | 0 | 2625 | 4375 | 7125 | 10500 |
3 | x | x | 0 | 750 | 2500 | 5357 |
4 | x | x | x | 0 | 1000 | 3500 |
5 | x | x | x | x | 0 | 5000 |
6 | x | x | x | x | x | 0 |
① m[1,6]
A₁(A₂A₃A₄A₅A₆) = m[1,1] + m[2,6] + p₀p1₁p₆ = 36750
A₁A₂(A₃A₄A₅A₆) = m[1,2] + m[3,6] + p₀p1₂p₆ = 32357
A₁A₂A₃(A₄A₅A₆) = m[1,3] + m[4,6] + p₀p1₃p₆ = 15125
A₁A₂A₃A₄(A₅A₆) = m[1,4] + m[5,6] + p₀p1₄p₆ = 21875
A₁A₂A₃A₄A₅)A₆) = m[1,5] + m[6,6] + p₀p1₅p₆ = 26875
마지막 메트릭스까지 채웠을 때 결과를 확인하면 ((A₁(A₂A₃))((A₄A₅)A₆))가 최적화된 해가 됩니다.
◡̈
'Algorithm' 카테고리의 다른 글
[Algorithm] 배낭문제, 냅색(Knapsack)이란? (0) | 2023.04.18 |
---|---|
[Algorithm] Greedy로 Huffman code 풀기 (0) | 2023.04.18 |
[Algorithm] 마스터 정리 (Master Theorem) (0) | 2023.04.16 |
[Algorithm] 재귀 트리(Recursion Tree Theorem) (0) | 2023.04.16 |
[Algorithm] 점근적 표기법(Asymptotic notation) 이해하기 (0) | 2023.04.16 |