행렬 곱셈 순서
-
연쇄 행렬 곱셈 (Matrix chain multiplication) :: 마이구미알고리즘 2017. 11. 27. 00:14
이 글은 연쇄 행렬 곱셈(Matrix chain multiplication) 알고리즘을 다룬다.동적계획법이 기반으로 된 알고리즘이다.위키 내용과 관련 알고리즘 문제를 참고했다. (위키는 번역본이 아직 없다)참고 링크 - https://en.wikipedia.org/wiki/Matrix_chain_multiplication 연쇄 행렬 곱셈은 최적화 문제를 동적계획법(DP) 을 이용하여 해결할 수 있다.행렬의 순서가 주어질 때, 행렬의 곱셈에서 가장 효율적인 방법을 찾는 것이 목표이다.문제는 실제로는 곱셈을 수행하는 것이 아니라 행렬의 곱셈 순서를 결정하는 것이다. 행렬 곱셈에 있어서, 괄호를 어디에 넣어도 같은 결과를 만든다.이것이 의미하는 것은 예를 통해 확인해보자.4개의 행렬 A, B, C, D 를 가..