연쇄행렬알고리즘 #동적계획법 #알고리즘

[알고리즘] 동적 계획법 | 연쇄 행렬 곱셈

동적 계획법을 복습할겸 연쇄 행렬 곱셈에 대해 다시 한 번 정리하고자 한다. 연쇄 행렬 곱셈 문제가 뭔데? 주어진 n 개의 연쇄 행렬을 곱하는 최적의 순서를 구하시오. n 개의 연쇄 행렬 곱셈: A1 * A2 * ...* An [행렬 곱셈은 결합 법칙이 성립한다!] 예를 들어, (Ax * Ay) * Az = Ax * (Ay * Az) 이렇게 곱셈 순서를 바꾸어도 계산 결과가 같다는 뜻이다. 그러나 중요한 점은 행렬 곱셈의 순서에 따라 각 원소의 곱셈 횟수가 달라진다는 것이다. 그렇다면 최적의 순서는 곱셈의 횟수가 가장 작아지도록 하는게 최적일 것이다. 즉 이 문제는 최적화 문제라는 뜻이다. -> 원소의 곱셈 횟수를 최적화하는 문제를 찾아보도록하자. 연쇄 행렬 곱셈 문제를 이해해보자! 2 * 3 행렬과 3..