Chained Matrix Multiplication (1) 썸네일형 리스트형 [알고리즘] 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication) 연쇄 행렬 곱셈 알고리즘(Chained Matrix Multiplication) 연쇄 행렬(ex, 2 by 4 행렬 x 4 by 7 행렬 x 7 by 9 행렬 x ...)의 곱셈을 할 때 곱셈 연산을 최소로 하는 곱셈 순서를 찾는 알고리즘이다. 행렬 곱셈은 결합 법칙이 성립하기 때문에 곱하는 순서에 상관은 없지만, 순서에 따라 연산의 양이 달라진다. 2 x 3 행렬 A와 3 x 5 행렬 B, 5 x 7 행렬 C가 있다고 하자. 이 행렬들의 곱 ABC를 구하는 경우는 아래와 같다. 1. AB를 먼저 곱하고 C를 곱할 때의 연산 수 = 2 x 3 x 5 + 2 x 5 x 7 = 100 2. BC를 먼저 곱하고 A를 곱할 때의 연산 수 = 3 x 5 x 7 + 2 x 3 x 7 = 147 둘은 같은 곱셈이지만.. 이전 1 다음