문서 보기문서 편집수정 내역 연쇄 행렬 곱셈 알고리즘 (덤프버전으로 되돌리기) [[분류:알고리즘]] [목차] == 설명 == 연쇄 [[행렬곱|행렬 곱셈]] (Chained Matrix Multiplication) 문제는 주어진 연쇄 행렬의 곱셈을 할 때, 각 원소의 곱셈 횟수를 최소로 하는 곱셈의 순서를 찾는 최적화 문제이다. 예를 들어, 4개의 행렬을 곱하는 ABCD의 경우를 생각해 보자. 행렬 곱셈은 [[결합법칙]]이 성립하므로, 행렬을 곱하는 순서는 상관이 없다. {{{#!wiki style="text-align: center;" [math(\begin{aligned}((AB)C)D& = (A(BC))D = (AB)(CD)\\& = A((BC)D) = A(B(CD)) \end{aligned})]}}} 하지만 각 행렬의 행과 열의 크기에 따라 각 원소를 곱하는 횟수는 서로 달라진다. [[https://www.acmicpc.net/problem/11049|BOJ의 이 문제]]를 보면 알 수 있다. 연쇄 행렬 곱셈 알고리즘은 연쇄 형렬 곱셈 문제를 풀어, 가장 효율적으로 행렬을 곱하는 순서를 찾는 알고리즘이다. 이 알고리즘은 [[동적 계획법]]과 [[메모이제이션]]으로 풀 수 있는 대표적인 알고리즘으로 알고리즘 교재에 자주 등장한다. == 동적 계획법의 적용 == 연쇄 행렬 곱셈 알고리즘은 먼저 재귀 관계를 찾은 후에 이차원 배열을 이용하여 상향식으로 동적계획법을 적용하면, --그까이꺼 대충-- 다음과 같이 구현할 수 있다. {{{#!syntax python def minmult (d): n = len(d) - 1 M = [[-1] * (n + 1) for _ in range(n + 1)] P = [[-1] * (n + 1) for _ in range(n + 1)] for i in range(1, n + 1): M[i][i] = 0 for diagonal in range(1, n): for i in range(1, n - diagonal + 1): j = i + diagonal M[i][j], P[i][j] = minimum(M, d, i, j) return M, P def minimum (M, d, i, j): minValue = INF minK = 0 for k in range(i, j): value = M[i][k] + M[k + 1][j] value += d[i - 1] * d[k] * d[j] if (minValue > value): minValue = value minK = k return minValue, minK }}} 위의 소스 코드 구현에 대한 상세한 설명은 [[https://youtu.be/5MXOUix_Ud4|이 영상]]에서 볼 수 있다. [* [[https://youtu.be/5MXOUix_Ud4|연쇄 행렬 곱셈 유튜브 강의 영상]]]캡챠되돌리기