[알고리즘] 동적 계획법(Dynamic Programming) - 4

동적 계획법(Dynamic Programming) - 4

이번에는 동적 계획법 알고리즘에서 가장 유명한 알고리즘인 Matrix chain multiple을 알아보자

이것은 말그대로 두 행렬을 곱하는 알고리즘이다.

위의 코드는 pxq인 A 행렬과 qxr인 B 행렬의 곱하기 이다.

3개의 반복문으로 돌아가며 곱셈 연산의 횟수는 pqr번이고 결과값은 C에 저장된다.

그러나 우리가 지금 하려는 것은 Matrix chain이다. ABCD의 행렬을 차례로 곱해야 하는 것이다.

행렬은 결합 법칙이 성립하므로 계산 순서에 따라서 곱셉 연산의 횟수가 달라진다.

그럼 n개의 행렬을 곱할 때 최적의 순서는 무엇일까

이 문제를 동적 계획법으로 접근할때 어떻게 풀어야 하는지를 생각해보면,

subproblem으로 나눠서 optimal substructure를 확인해야 한다.

따라서 이것은 계산 순서를 찾는 것이므로, 최적의 계산 순서를 가정한 후에 맞는지 확인해야한다.

n개의 행렬을 곱하는 것은 최종적으로 1개의 행렬이 된다.

그리고 1개의 행렬이 나오기 전에는 2개의 행렬이 있다.

그러므로 X와 Y를 곱해서 Z가 되었다면 A1에서 어딘가까지가 X, 어딘가에서 An까지의 곱이 Y가 되는 것이다.

만약 이것이 최적해라면, X나 Y를 구하는 과정도 최적해가 되어야한다.

이는 비교적 단순한 optimal substructure이다.

m[i,j]는 행렬 Ai에서 Aj까지 곱하는 최소 곱셈의 횟수가 된다.

그러므로 i가 j보다 작다면, i에서 k 까지를 최선으로 곱할때의 계산량과 k+1에서 j까지 곱할때의 계산량을 더한다.

마지막으로 그 두개를 곱하는 비용(Pi-1*Pk*Pj)까지 계산해서 더해지면 최소곱셈의 횟수가 나오게 된다.

이것이 순환식으로 올바르게 동작하기 위해서는 base case가 필요한데,

i, j의 간격이 점점 좁아지기 때문에, i와 j가 0이 될경우를 base case로 정의한다.

i, j가 같다는 것은 행렬이 1개만 있다는 것이므로 계산량이 0이다. 따라서 0을 리턴한다.

위의 코드가 Matrix chain multiple에 대한 코드이다.

3개의 반복문으로 인해 시간복잡도는 ø(n^3)이 된다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘