[알고리즘] 동적 계획법 - 연쇄 행렬곱셈 (Chained Matrix Multiplication)
우선 2x3 행렬과 3x4 행렬을 곱해봅시다. 결과물은 2x4 행렬이 나오겠죠? 또한 곱셈의 횟수는 2 x 3 x 4 = 24입니다. 즉 i x j 행렬과 j x k행렬의 곱의 횟수는 i x j x k가 됩니다. 또 다른 예시를 들어봅시다. A X B X C X D이고, A = 20 x 2, B = 2 x 30, C = 30 x 12, D = 12 x 8입니다. 행렬 곱셈은 결합 법칙이 성립하므로, 곱셈의 순서는 결과에 영향을 미치지 않습니다. 즉, (AB)(CD) = (A(B(CD))와 같습니다. 이때 4개의 행렬은 총 5개의 다른 순서로 곱할 수 있습니다. A(B(CD)) : 3680 A((BC)D) : 1232 (AB)(CD) : 8880 ((AB)C)D : 10320 (A(BC))D : 3120 ..