배경
여러 행렬을 연속해서 곱할 때, 가능한 순서는 굉장히 많다. 예를 들어, A, B, C, D, 총 4개의 행렬을 곱하는 경우, 다음의 조합이 가능하다:
(AB)(CD)
((AB)C)D
(A(BC))D
A((BC)D)
A(B(CD))
그리고 각 순서에 따라 필요한 곱셈 연산의 수도 크게 차이가 난다. 아래를 참고하자:
A = 20 * 2, B = 2 * 30, C = 30 * 12, D = 12 * 8 크기일 때,
(AB)(CD) = 3k 회의 연산 필요
((AB)C)D = 8k 회의 연산 필요
(A(BC))D = 1k 회의 연산 필요
A((BC)D) = 10k 회의 연산 필요
A(B(CD)) = 3k 회의 연산 필요
따라서 주어진 배열들의 크기를 고려하여, 최대한 적은 연산 횟수를 갖는 곱셈 순서를 찾아내야 한다. 다만 지금은 DP를 활용하는 게 더 중요하므로, 곱셈 순서는 고려하지 않고 최소 연산 횟수를 계산하는 데 중점을 두고자 한다.
접근
동적 계획법은 보통 아래의 절차로 진행되는 경우가 많다:
- 문제에서 재귀적 특성을 찾아 수학적으로 정의하기
- 코드로 변환하여 작은 문제부터 큰 문제까지 풀기
그런데 사실 1번 과정이 제일 어려운 경우가 많다. 수학적이지 않아 보이는 문제나 상황을 수학적으로 변환해야 하기 때문이다. 그럴 때에는, 비교적 작은 n을 입력으로 하여 간단히 계산을 해 보고, 그 결과에서 규칙을 찾아보는 게 더 좋은 접근일 수도 있다.
> 0. 비교적 작은 문제를 직접 풀어 규칙 추측하기
1. 문제에서 재귀적 특성을 찾아 수학적으로 정의하기
2. 코드로 변환하여 작은 문제부터 큰 문제까지 풀기
의사 코드?
곱하는 행렬 사이의 거리가 1인 경우:
A0부터 A2까지 3개의 배열이 있을 때, A0 * A1은 가능한 순서의 수가 1개밖에 없으므로 DP 적용하지 않고 바로 연산한다.
곱하는 행렬 사이의 거리가 2 이상인 경우:
위에서 계산한 값을 바탕으로 연산한다.
A0부터 A2까지 3개의 배열이 있을 때, (A0 * A1) * A2와 A0 * (A1 * A2)의 2가지 경우의 수가 있다. 이 때 위에서 계산한 (A0 * A1)과 (A1 * A2)의 연산 수에, (A0 * A1)을 계산해 나온 행렬과 A2를 곱하는 데 필요한 연산 수까지 추가로 더해주어야 한다.
예를 들어, A0 = 5 * 2, A1 = 2 * 3, A2 = 3 * 4라고 하자. (A0 * A1)에는 5 * 2 * 3 = 30회의 연산이 필요하다. 그리고 계산 결과는 5 * 3의 행렬이다. 우리는 이 행렬에 3 * 4 크기의 행렬을 또 곱해야 한다. 따라서 우리는 5 * 3 * 4 = 60회의 연산을 추가로 실행해야 한다. 최종적으로는 30회 + 60회 = 90회의 연산이 필요하다는 말.
Python 코드
동적 계획법
import copy
def cmm_dp(arr: list) -> int:
length = len(arr) - 1
matrix = [copy.deepcopy([0] * length) for _ in range(length)]
step = 1
while step < length:
for n in range(step, length):
if (step == 1):
matrix[n][n - 1] = arr[n - 1] * arr[n] * arr[n + 1]
else:
x = n
y = n - step
p = matrix[x - 1][y] + arr[y] * arr[x] * arr[x + 1]
q = matrix[x][y + 1] + arr[y] * arr[y + 1] * arr[x + 1]
matrix[x][y] = min(p, q)
step += 1
return matrix[-1][0]행렬의 크기 나타내기
나는 1차원 배열에 행렬 크기를 저장했다.
배열 An의 크기를 d0 * d1이라고 했을 때, A0 = d0 * d1, A1 = d1 * d2, ..., 이런 식으로 규칙을 이룰 것이다. 이 때, 굳이 d1을 두 번 저장할 필요가 없다고 생각해서 그냥 1차원 배열에 d0, d1, ..., 이런 식으로 저장했다.
표에 적으면 이런 식으로 나오는데, 예를 들어 배열 A0의 크기는 5 * 2이고, 배열 A1의 크기는 2 * 3이고, ..., 배열 A5의 크기는 7 * 8이고... 이런 식으로 이해하면 된다.
시간 복잡도
무차별 대입
행렬 A1, A2, ..., An이 존재할 때, 이 행렬들을 곱할 때 가능한 순서의 개수를 Tn이라고 하자. 이 때, A1 * (A2 * ... * An)으로 행렬을 나누면, (A2 * ... * An)에서 가능한 순서의 개수는 Tn-1이다. 또한, (A1 * ... * An-1) * An으로 행렬을 나눠도 가능한 순서의 개수는 Tn-1이다. 따라서, Tn >= Tn-1 + Tn-1 = 2Tn-1이다.
한편, 행렬이 두 개 있을 때 가능한 순서의 개수는 오직 1개밖에 없다. 따라서 T2 = 1이다.
이상의 두 가지 조건을 바탕으로 계산하면, Tn >= 2^n-2이라는 부등식이 도출된다. 따라서 연속된 행렬의 곱셈에서 연산의 수가 가장 적은 순서를 무차별 대입법으로 찾아내는 경우에 대해서, O(2^n)의 시간 복잡도가 필요하다.
동적 계획법
자고 일어나서 정리하도록 하자...
