문제 요약
여러 개의 행렬을 순서는 유지한 채 모두 곱하려고 한다.
행렬을 곱하는 괄호 위치에 따라 필요한 곱셈 연산 횟수가 달라진다.
모든 행렬을 곱하기 위한 최소 연산 횟수를 구해야 한다.
크기가 a x b인 행렬과 b x c인 행렬을 곱하는 비용은 다음과 같다.
a x b x c핵심 아이디어
행렬의 순서는 고정되어 있으므로, 어떤 구간을 중간 어디에서 두 부분으로 나눌지만 결정하면 된다.
예를 들어 A, B, C, D를 곱할 때 A부터 D까지의 최적 비용은 다음 분할 중 하나다.
A | BCD
AB | CD
ABC | D이를 구간 DP로 표현한다.
dp[start][end]
= start번 행렬부터 end번 행렬까지 곱하는 최소 연산 횟수구간을 mid에서 나누면 비용은 다음 세 부분의 합이다.
왼쪽 구간의 최소 비용
+ 오른쪽 구간의 최소 비용
+ 두 결과 행렬을 마지막으로 곱하는 비용행렬 곱셈 비용
행렬 i부터 j까지의 구간을 mid에서 나눈다고 하자.
(행렬 i ... 행렬 mid) x (행렬 mid + 1 ... 행렬 j)왼쪽 결과 행렬의 크기는 다음과 같다.
matrix_sizes[i][0] x matrix_sizes[mid][1]오른쪽 결과 행렬의 크기는 다음과 같다.
matrix_sizes[mid + 1][0] x matrix_sizes[j][1]입력 행렬은 항상 곱할 수 있으므로 두 결과 행렬을 곱하는 비용은 다음과 같다.
matrix_sizes[i][0] * matrix_sizes[mid][1] * matrix_sizes[j][1]점화식
행렬 i부터 j까지의 최소 비용은 가능한 모든 분할 위치를 확인해 구한다.
dp[i][j] = min(
dp[i][mid]
+ dp[mid + 1][j]
+ matrix_sizes[i][0]
x matrix_sizes[mid][1]
x matrix_sizes[j][1]
)mid는 i부터 j - 1까지의 모든 위치가 될 수 있다.
for mid in range(start, end):행렬 하나만 있는 구간은 곱셈이 필요 없다.
dp[i][i] = 0구간 길이 순서
dp[start][end]를 계산하려면 더 짧은 두 구간의 값이 먼저 계산되어 있어야 한다.
따라서 구간 길이를 짧은 것부터 늘려 간다.
길이 1: 행렬 하나, 비용 0
길이 2: 인접한 행렬 두 개
길이 3: 행렬 세 개
...
길이 N: 전체 행렬풀이 과정
- N x N 크기의 DP 배열을 0으로 초기화한다.
- 길이가 2인 구간부터 전체 길이까지 순회한다.
- 각 구간의 모든 분할 위치를 확인한다.
- 왼쪽 비용, 오른쪽 비용, 마지막 곱셈 비용을 더한다.
- 가장 작은 비용을 해당 구간의 DP 값으로 저장한다.
- 전체 구간의 DP 값을 반환한다.
Python 코드
def solution(matrix_sizes):
matrix_count = len(matrix_sizes)
# dp[start][end]:
# start번 행렬부터 end번 행렬까지 곱하는 최소 비용
dp = [
[0] * matrix_count
for _ in range(matrix_count)
]
# 짧은 구간부터 최소 비용을 계산한다.
for length in range(2, matrix_count + 1):
for start in range(matrix_count - length + 1):
end = start + length - 1
dp[start][end] = float("inf")
# start ~ end 구간을 mid 기준으로 나눈다.
for mid in range(start, end):
multiply_cost = (
matrix_sizes[start][0]
* matrix_sizes[mid][1]
* matrix_sizes[end][1]
)
cost = (
dp[start][mid]
+ dp[mid + 1][end]
+ multiply_cost
)
dp[start][end] = min(
dp[start][end],
cost
)
return dp[0][matrix_count - 1]코드 설명
dp 배열
dp[start][end]start번 행렬부터 end번 행렬까지 하나의 행렬로 만들기 위한 최소 곱셈 연산 횟수다.
행렬 하나는 이미 완성된 행렬이므로 비용이 0이다.
dp[i][i] = 0구간 길이
for length in range(2, matrix_count + 1):길이 2인 구간을 먼저 계산하면 길이 3인 구간에서 필요한 부분 결과를 사용할 수 있다.
이 방식으로 길이를 늘려 가면 필요한 짧은 구간이 항상 먼저 계산되어 있다.
분할 위치
for mid in range(start, end):mid는 왼쪽 그룹의 마지막 행렬 번호다.
예를 들어 start가 0, end가 2라면 다음 두 경우를 확인한다.
mid = 0: A | BC
mid = 1: AB | C마지막 행렬 곱셈 비용
matrix_sizes[start][0]
* matrix_sizes[mid][1]
* matrix_sizes[end][1]왼쪽 결과 행렬의 행 크기는 시작 행렬의 행 크기다.
오른쪽 결과 행렬의 열 크기는 끝 행렬의 열 크기다.
두 결과 행렬의 공통 차원은 왼쪽 구간 마지막 행렬의 열 크기다.
예시
다음 행렬들을 생각해보자.
A: 5 x 3
B: 3 x 10
C: 10 x 6A와 B를 먼저 곱하면 다음 비용이 필요하다.
(A x B) x C
A x B: 5 x 3 x 10 = 150
AB x C: 5 x 10 x 6 = 300
총 비용: 450B와 C를 먼저 곱하면 다음 비용이 필요하다.
A x (B x C)
B x C: 3 x 10 x 6 = 180
A x BC: 5 x 3 x 6 = 90
총 비용: 270따라서 최솟값은 270이다.
시간 복잡도
행렬의 개수를 N이라고 하자.
구간 길이, 구간 시작점, 분할 위치를 각각 순회한다.
O(N^3)N은 최대 200이므로 약 800만 번 수준의 분할 비용 계산으로 처리할 수 있다.
공간 복잡도
N x N 크기의 DP 배열을 사용한다.
O(N^2)정리
이 문제는 행렬의 순서를 유지하면서 괄호를 어디에 둘지 결정하는 구간 DP 문제다.
dp[start][end]를 구간의 최소 비용으로 정의
구간을 가능한 모든 위치에서 두 부분으로 분할
왼쪽 최소 비용 + 오른쪽 최소 비용 + 마지막 곱셈 비용 계산
더 짧은 구간부터 계산
전체 구간의 최소 비용 반환행렬의 실제 곱셈 결과를 만들 필요 없이, 각 구간의 결과 행렬 크기와 최소 비용만 관리하는 것이 핵심이다.
