동적계획 (1) 썸네일형 리스트형 Chap 5-2.연속 행렬 곱셈 연속 행렬 곱셈(Chained Matrix Multiplication) 문제 = 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제 행렬 곱셈 (1) 두 행렬의 곱셈이란? 두 행렬 A, B가 있다. A = 10 x 20 B = 20 x 5 라면 총 곱셈의 횟수 = 10 * 20 * 5 = 1000이다. (2) 3개의 행렬 곱셈 A = 10 x 20 B = 20 x 5 C = 5 x 15 행렬의 곱셈은 결합법칙 성립하므로 (A* B) * C , A * ( B * C) 이 둘 다 성립한다. 하지만 둘의 결과값는 같지만 곱셈의 횟수는 전자가 더 적다.(과정이 다르다) [ 행렬 곱셈의 주의점 ] 주어진 행렬의 순서를 지켜서 “반드시 이웃하는 행렬끼리” 곱해야 한다. 동적 알고리즘 적용 (1) .. 이전 1 다음
