[알고리즘-공부] 5.동적계획법(2) - 연속행렬곱셈

코드로는 이해가 잘 안간다. 책을 봐도 읽기 싫게 생겼다.. 그냥 문제를 풀면서 한번 생각해 보자

우선 책을 읽고 문제를 접하는게 이해하기 쉬울것 같다. 이 알고리즘은 결합법칙이 핵심인것 같다.

 

첫번째 문제  A1 (10 x 2), A2 (2 x 20), A3 (20 x 5), A4 (5 x 15)

1. 일단 행렬 (1,1) ,(2,2), (3,3), (4,4)에 모두 0을 집어 넣자

2. 첫번째 사선인 (1,2), (2,3), (3,4)의 행렬값을 채워 나가자

A1A2 = (10 x 2) x (2 x 20) = (10 x 20), A1A2의 값 : 10 x 2 x 20 = 400

A2A3 = (2 x 20) x (20 x 5) = (2 x 5), A2A3의 값 : 2 x 20 x 5 = 200

A3A4 = (20 x 5) x (5 x 15) = (20 x 15), A3A4의 값 : 20 x 5 x 15 = 1500

 3. 두번째 사선인 (1,3), (2,4)의 행렬 값을 채워 나가자

(※ 여기서(1,3)은 A1A2A3 3개의 행렬값 즉, 1~3까지의 행렬값을 의미 한다.)

(※ 3개의 행렬 곱부터는 "결합법칙"을 생각해서 더 작은 값을 선택해야 한다.)

(1) (1,3) 행렬 값 구하기

(A1A2)A3 = (10 x 20) x (20 x 5) = (10 x 5), A1A2A3의 값 : 10 x 20 x 5 = 1000, 여기에 A1A2의 값인 400을 더한다.

                  결국(A1A2)A3의 결과값 = 1400 

A1(A2A3) = (10 x 2) x (2 x 5) = (10 x 5), A1A2A3의 값 : 10 x 2 x 5 = 100, 여기에 A2A3의 값인 200을 더한다.

                  결국A1(A2A3)의 결과값 = 300 pick

  => 두개 중에 1400 > 300이고 우리는 곱셈수가 적은 300을 선택한다.

(2) (2,4) 행렬 값 구하기

(A2A3)A4 = (2 x 5) x (5 x 15) = (2 x 15), A2A3A4의 값 : 2 x 5 x 15 = 150, 여기에 A2A3의 값인 200을 더한다.

                  결국(A2A3)A4의 결과값 = 350 pick

A2(A3A4) = (2 x 20) x (20 x 15) = (2 x 15), A2A3A4의 값 : 2 x 20 x 15 = 600, 여기에 A3A4의 값인 1500을 더한다.

                  결국A2(A3A4)의 결과값 = 2100

  => 두개 중에 2100 > 350이고 우리는 곱셈수가 적은 350을 선택한다.

 4. 마지막 행렬값인 (1,4)를 채워보자

원래는 A1A2A3A4는  ((A1A2)A3)A4,  (A1(A2A3))A4,  A1(A2(A3A4))....등 많은 경우의 수를 따져서 값을 구해야 한다. 그러나 우리는 3번째 행렬 3개씩 곱하는 부분에서 (A2A3)을 결합하면 가장 적은 수를 구할 수 있다는 힌트를 얻었다. 이 힌트 덕분에 우리는  (A1(A2A3))A4,  A1((A2A3)A4) 이 두가지 경우만 생각하면 된다. 

(1) (A1(A2A3))A4

(10 x 2)(2 x 5)(5 x 15) = (10 x 2)(2 x 5) = (10 x 5), (A1(A2A3))의 값 : 10 x 2 x 5 = 100

                                     (10 x 5)(5 x 15) = (10 x 15),  (A1(A2A3))A4의 값 : 10 x 5 x 15 = 750 

                                     (A2A3)의 값 : 200

                                     총 100+750+200 = 1050

(2) A1((A2A3)A4)

(10 x 2)(2 x 5)(5 x 15) = (2 x 5)(5 x 15) = (2 x 15), (A2(A3A4))의 값 : 2 x 5 x 15 = 150

                                     (10 x 2)(2 x 15) = (10 x 15),  A1((A2A3)A4)의 값 : 10 x 2 x 15 = 300 

                                     (A2A3)의 값 : 200

                                     총 150+300+200 = 650

 

=>결국 A1((A2A3)A4)이 더 적은 수를 곱하게 되므로 행렬(1,4)의 값은 650이된다.

 

 

두번째 문제  A1 (10 x 20), A2 (20 x 5), A3 (5 x 15), A4 (15 x 30)

빠르게 한번 구해보자

 

A1A2 = (10 x 20) (20 x 5) = (10 x 5), 10 x 20 x 5 = 1000

A2A3 = (20 x 5) (5 x 15) = (20 x 15), 20 x 5 x 15 = 1500

A3A4 = (5 x 15) (15 x 30) = (5 x 30), 5 x 15 x 30 = 2250

 

(A1A2)A3 = (10 x 5) (5 x 15) = 10 x 5 x 15 = 750, (A1A2)의 값 = 1000,    ∴ (A1A2)A3의 값 = 1750 (pick)

A1(A2A3) = (10 x 20) (20 x 15) = 10 x 20 x 15 = 3000, (A2A3)의 값 = 1500,    ∴ A1(A2A3)의 값 = 4500

 

(A2A3)A4 = (20 x 15) (15 x 30) = 20 x 15 x 30 = 9000, (A2A3)의 값 = 1500,    ∴ (A2A3)A4의 값 = 10500

A2(A3A4) = (20 x 5) (5 x 30) = 20 x 5 x 30 = 3000, (A3A4)의 값 = 2250,    ∴ A2(A3A4)의 값 = 5250 (pick)

 

결국 (A1A2)(A3A4)가 가장 빠르다는 것을 알았고, 값을 구하면 (10 x 5) (5 x 30) = 10 x 5 x 30 = 1500이고 여기에

(A1A2)의 값 1000과 (A3A4)의 값 2250을 더하면 4750이 된다.

 

마지막 문제  A1 (5 x 4), A2 (4 x 6), A3 (6 x 2), A4 (2 x 7)

위에 방식처럼 풀면 이렇게 나오네요!ㅎㅅㅎ 다들 열공하세요~~

 

 

 

출처 : [알기쉬운 알고리즘-양성봉] 전공책입니다.