알고리즘 #6_ 동적 프로그래밍: 행렬 체인 곱셈(Matrix-chain Multiplication)

이번 포스팅에서는 동적 프로그래밍의 세번째 예제인 행렬 체인 곱셈(Matrix-chain Multiplication)에 대해서 알아보도록 하겠습니다.

---

1. 행렬 체인 곱셈(Matrix-chain Multiplication)

이번 세번째 예제인 행렬 체인 곱셈(Matrix-chain Multiplication)문제는 n개의 행렬을 곱하는 것에 대한 문제입니다.

먼저 행렬의 곱은 아래의 수도코드와 같은 방식으로 진행됩니다.

위의 수도코드를 보면 A행렬이 p*q이고 B행렬이 q*r일때, 이 두 행렬의 곱을 통한 새로운 행렬 C를 계산하는데 걸리는 시간은 수도코드의 8행에 따른 곱셈의 횟수, pqr번에 의해서 결정됩니다.

예를들어, 아래와 같은 세개의 행렬이 있을 때, 두가지 방법의 곱셈이 가능할 것입니다.

A1와 A2를 먼저 계산한다면 총 840번의 곱을 수행해야 합니다.

하지만 A2와 A3를 먼저 계산한다면 총 460번의 곱을 수행하면 됩니다.

따라서 행렬 체인 곱셈 문제에서는 행렬을 곱할 때 비용이 가장 적은 순서를 찾아내는 것이 목표입니다.

2. Brute-force 방식

지난 두 예제에서 알아본 것과 같이, 동적 프로그래밍을 적용한 해결 방법을 살펴보기전에 모든 경우의 수를 조사하는 brute-force방식을 살펴보도록 하겠습니다.

n개의 행렬을 괄호로 묶는 서로 다른 방법의 수를 P(n)이라고 함ㄴ다면, n이 1일 때에는 행렬이 한 개뿐인 것이므로 괄호를 묶는 방법은 단 한가지 입니다. n이 2보다 크거나 같을 때, 행렬 전체를 완전하게 괄호로 묶는 방법의 수는 두개의 완전하게 괄호로 묶인 두 부분 곱들의 곱이고, 두 개의 부분 곱 사이를 나누는 것은 1과 n-1의 값, k번째와 k+1번째 행렬의 사이가 됩니다. 이를 통해 아래의 점화식을 얻을 수 있습니다.

위의 식을 분석해보면 점화식의 해가 대략 개를 가지는 것을 알 수 있습니다.

3. 동적 프로그래밍으로 행렬 체인 곱셈 문제 해결하기

먼저 행렬 체인 곱셈 문제의 최적 부분 구조를 생각해보면 다음과 같습니다.

를 괄호로 최적으로 묶기 위해 와 의 사이에서 나눈다고 생각해보겠습니다. 그렇다면 앞의 부분 곱, 을 확인하였을 때, 의 괄호 묶는 방법은 의 최적의 괄호 묶는 방법으로 되어야 할 것 입니다.

즉, 최적의 괄호를 묶기 위해서 부분 곱에서 또한 같은 특징이 성립되어 부분 곱도 괄호 묶기에 대해 서로 최적이어야 합니다.

따라서 m[i,j]는 다음과 같이 정의됩니다.

그리고 m[i,j]는 다음과 같은 점화식을 통해 값이 구성됩니다.

이렇게 구한 m은 행렬 곱셈을 계산하는데 필요한 최적의 계산 수를 저장합니다.

하지만 행렬을 곱하는 방법을 제공하지는 않기에 우리는 s라는 배열을 사용하여 필요한 정보를 저장합니다.

s[i,j] 에는 Ai행렬부터 Aj까지의 행렬을 곱할 때 마지막으로 괄호 묶기가 되는 와  의 k값을 저장합니다.

이러한 테이블과 점화식을 토대로 행렬 체인 곱셈문제를 해결하는 알고리즘은 다음과 같습니다.

위의 수도코드에서 4번라인까지는 테이블 m을 초기화하는 과정입니다.(길이가 1인 행렬 곱셈에 대한 최소비용은 0이므로)

이후 5번 라인에서 반복문이 시작되며 처음엔, i가 1부터 n-1까지 증가하는 동안 길이가 2인 행렬에 대한 최소 비용을 구하며, 두번째 반복에서는 i가 1부터 n-2까지 증가하는 동안 길이가 3인 행렬에 대한 최소비용을 구합니다. 이런식으로 반복문이 진행되고 이를 통해 수도코드의 총 시간복잡도는 이며, 테이블 m과 s를 저장하기 위해 필요한 공간 복잡도는 입니다.

A1부터 A6행렬까지 있는 곱셈을 계산하였을때 작성되는 테이블 m과 s는 아래와 같으며 중간 계산 중 일부가 아래에 나와 있으니 확인하시고 확실히 이해 하시길 바랍니다.

---

이렇게 해서 동적 프로그래밍의 세번째 예제, 행렬 체인 곱셈(Matrix-chain Multiplication)에 대해서도 알아보았습니다.

특히나 저는 행렬 체인 곱셈이 많이 헷갈리고 어려웠기에 추가적으로 확인하면서 더 간단하게 설명이 되는 부분은 수정하도록 하겠습니다.

이해가 잘 안되거나 궁금한 점은 언제든 댓글을 남겨주세요 :)