목록11049 (1)

JINWOOJUNG

[ DP-11049 ] 행렬 곱셈 순서(C++)

접근법 연쇄적인 행렬의 곱셈 순서를 결정하는 것은 DP 문제 중 하나로, 효율적은 행렬 곱셈 순서를 결정하는 문제이다. 문제에서 언급 되었듯이 행렬의 곱셈 순서에 따라서 요구되는 계산량이 달라지기 때문에, 곱셈 연산을 최소로 하는 순서를 결정해야 한다. 가장 기본적인 행렬 곱셈의 규칙을 생각 해 보자. $A$ 행렬은 $ i by j $, $B$ 행렬은 $k by l$이라 하면, 행렬 $A,B$의 곱셈 연산이 성립하기 위해서는 $j == k$여야 하며, 계산된 행렬을 $C$라 하면, $C$의 크기는 $ i by l $이 된다.  이러한 규칙을 고려하여, 연쇄 행렬곱셈을 DP를 이용하여 해결하기 위해서 재귀 관계식을 구축하면 다음과 같다. $$d_k = 행렬 A_k의 열의 수  /to  A_k의 행의 수는 ..
백준 2024. 5. 19. 22:40
이전 Prev 1 Next 다음