11049번 - 행렬 곱셈 순서(pypy3 풀이, python3 링크)

문제 링크 : www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

동적 계획법 공부할 때 꼭 나오는 문제 중 하나인 matrix-chain multiplication 문제입니다. 4개 행렬의 곱인 ABCD가 있을때 A*(B*C*D), (AB)*(CD), (A*B*C)*D 어떤 순서대로 계산하더라도 결과값은 같지만, 연산 횟수에서 차이가 날 수 있습니다. 문제에서 주어진 예시를 한 번 보죠.

 

3개의 행렬 A(5*3), B(3*2), C(2*6)가 있습니다. ABC를 구하기 위해서는 AB*C, A*BC 2가지 선택지가 있죠. 각각의 연산 횟수를 계산해봅시다.

1. AB*C : 5*3*2 + 5*2*6 = 90
2. A*BC : 3*2*6 + 5*3*6 = 126

1번 방법이 더 효율적임을 알 수 있습니다. 행렬이 3개인 경우야 간단하게 손으로 계산 가능하지만 행렬의 개수가 백 개 정도 되는 경우에는? 노가다를 뛸 수 없죠. 이를 DP를 이용해서 풀어봅시다.

 

주어진 문제에서의 가장 작은 부분문제는 두 행렬의 곱입니다. AB, BC같은 경우죠. ABC의 optimal 연산 횟수를 구하는데는 AB, BC의 결과를 가져와서 사용합니다. 이 때 AB, BC 중 더 optimal한 결과를 가져와서 사용하게 됩니다. DP의 조건인 overlapping subproblem, optimal substructure를 모두 만족합니다.

 

다음은 제가 풀이에 사용한 코드입니다. 개인적으로 공부하면서 직관적으로 와닿지 않는 문제였는데, 코드를 표 및 진행 과정과 함께 차근차근 보도록 합시다.

import sys

n = int(sys.stdin.readline())
lst = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [[0]*n for _ in range(n)] #2차원 배열 생성

for i in range(1, n): #i번째 대각선
    for j in range(n-i): #i번째 대각선의 j번째 열
        dp[j][j+i] = 2**31
        for k in range(j, j+i): #이전 단계 부분문제에서 현재 문제를 푸는 k가지 방법 비교
            dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + lst[j][0]*lst[k][1]*lst[j+i][1])

print(dp[0][n-1])

DP로 풀기 위해 2차원 배열을 이용합니다. 행렬이 4개인 경우를 예로 봅시다. 표 M[i][j]는 i번째 행렬부터 j번째 행렬까지의 곱의 optimal 연산 횟수입니다. M[0][2]는 ABC의 optimal 연산 횟수가 되고, 우리의 목표는 optimal M[0][3]값을 구하는 것입니다.

행렬 크기 : A(5*3), B(3*2), C(2*6), D(6*4)

	0	1	2	3
0	0	a	b	c
1	0	0	a	b
2	0	0	0	a
3	0	0	0	0

 

같은 행렬을 곱하는 건 의미가 없으니 M[i][i] = 0이고, 거꾸로 행렬곱을 할 일도 없으니 M[i][j](i>j)인 부분도 모두 0입니다. 최종적으로 4개 행렬의 곱 연산 횟수를 구할 것이니까 2개 행렬의 곱, 3개 행렬의 곱, 4개 행렬의 곱을 차례대로 풀게 됩니다.

 

Knapsack 문제 같은 경우 n개의 물건을 고려하는 상황에서 가방 용량을 늘리게 되면 row를 n으로 고정시키고 column을 하나씩 늘려가면서 계산하면 되는데, 이 문제의 경우는 n개 행렬의 곱을 고려하는 상황이면 특정 row나 column을 고정시키지 않고 부분문제 단계 당 "하나의 대각선" 상에서 계산을 진행하게 됩니다.

 

이중 for문을 통해 가장 왼쪽의 대각선(가장 작은 부분문제들의 집합)부터 계산을 진행하게 됩니다.

 

1번째 대각선

2개 행렬의 곱(AB, BC, CD)의 optimal 연산 횟수는 표에서 빨간색 a로 표시한 곳에 저장되게 됩니다. 코드에서 i=1인 경우입니다.

 

i=1인 경우 j는 0~2까지의 값을 가집니다. 이 j는 i번째 대각선에서 몇 번째 열을 계산하는지 나타냅니다. 즉, 첫 번째 대각선에서 순서대로 첫 번째 열(M[0][1]), 두 번째 열(M[1][2]), 세 번째 열(M[2][3])의 optimal 값을 계산할겁니다. M[0][1]의 업데이트 과정을 예로 봅시다.(i=1, j=0)

 

문제에서 주어진 최악 연산 횟수가 2^31-1이니 현재 보고있는 칸(M[j][j+1] = M[1][0])의 값을 2^31로 초기화합니다. 이후 k번만큼(j~j+i) 값을 비교하며 업데이트하게 되는데, 이 때 k는 현재 문제까지 도달할 수 있는 부분문제의 개수입니다. AB를 구하는데 가능한 경우의 수는 1개이므로 현재 가능한 k값은 1 한 개입니다.

dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + lst[j][0]*lst[k][1]*lst[j+i][1])

dp[j][j+i]는 기존 값이니 넘어가고, 오른쪽 숫자 3개의 합으로 이루어진 곳을 봅시다. i=1, j=0인 경우에 오른쪽 값은 다음과 같이 나타납니다.

dp[0][0] + dp[1][1] + lst[0][0]*lst[0][1]*lst[1][1]

앞의 두 값은 0이고, 뒤쪽의 값은 A*B 행렬의 연산횟수 그 자체임을 알 수 있습니다. 앞의 두 값이 어떤 의미를 가지는지 알아보기 위해 다음 대각선으로 넘어가봅시다.

 

2번째 대각선

i = 2인 경우입니다. 이 때 가능한 j = 0, 1이고, 이번 단계에서는 M[0][2], M[1][3]을 업데이트하게 됩니다. 1단계를 마친 이후의 M은 다음과 같습니다.

	0	1	2	3
0	0	30	b	c
1	0	0	36	b
2	0	0	0	48
3	0	0	0	0

M[0][2]의 업데이트 과정을 봅시다.(j=0) 이 때 가능한 k값은 [0, 1] 2개입니다. ABC를 연산하는데는 A*(BC), (AB)*C 2가지 방법이 있습니다. BC를 먼저 계산하고 A*(BC)를 계산하는 비용과, AB를 먼저 계산하고 (AB)*C를 계산하는 비용을 비교해야 하는데, 여기서 AB와 BC를 계산하는 비용은 이미 1번째 대각선에서 구했으니, 이를 가져다 쓰면 됩니다.

 

1. k=0

dp[0][2] = min(dp[0][2], dp[0][0] + dp[1][2] + lst[0][0]*lst[0][1]*lst[2][1])

min의 오른쪽 값은 0, BC의 연산 횟수, A*BC의 연산 횟수의 합입니다. BC는 3*6 크기의 행렬이고, A*(BC)를 계산하는데 필요한 연산 횟수는 5*3*6이니, k=0인 경우에서는 BC를 구하는 부분문제에서 A*(BC) 문제로 가는 총 연산 횟수를 계산하게 됩니다.

 

2. k=1

dp[0][2] = min(dp[0][2], dp[0][1] + dp[2][1] + lst[0][0]*lst[1][1]*lst[2][1])

이 경우 min의 오른쪽 값은 AB의 연산 횟수, 0, AB*C의 연산 횟수의 합입니다. M[0][2]는 k=0, k=1인 경우를 비교하여 optimal한 값으로 결정됩니다.

 

3번째 대각선

i=3인 경우입니다. 가능한 j값은 0 하나이고, 구하고자 하는 전체 문제의 답인 M[0][3]을 구하게 됩니다. 2단계를 마친 이후의 M은 다음과 같습니다.

	0	1	2	3
0	0	30	90	c
1	0	0	36	72
2	0	0	0	48
3	0	0	0	0

ABCD를 계산하는데는 A*(BCD), (AB)*(CD), (ABC)*D 3가지 방법이 있습니다. 가능한 k값도 0, 1, 2 3개이니 각 k값이 현재 문제를 푸는 방법의 수를 나타낸다는 것을 알 수 있습니다.

 

1. k=0

dp[0][3] = min(dp[0][3], dp[0][0] + dp[1][3] + lst[0][0]*lst[0][1]*lst[3][1])

min의 오른쪽 값은 0, BCD의 연산 횟수, A*(BCD)의 연산 횟수의 합입니다.

 

2. k=2

dp[0][3] = min(dp[0][3], dp[0][2] + dp[3][3] + lst[0][0]*lst[2][1]*lst[3][1])

k=2인 경우를 먼저 봅시다. min의 오른쪽 값은 ABC의 연산 횟수, 0, (ABC)*D의 연산 횟수의 합입니다.

 

3. k=1

dp[0][3] = min(dp[0][3], dp[0][1] + dp[2][3] + lst[0][0]*lst[1][1]*lst[3][1])

min의 오른쪽 값은 AB의 연산 횟수, CD의 연산 횟수, (AB)*(CD)의 연산 횟수의 합입니다. k=0, 2일때와 다르게 2개의 부분문제(AB연산, CD연산)의 결과를 이미 구한 상태이므로 가져와서 사용합니다.

 

위 3가지 경우를 비교해서 가장 작은 값을 optimal한 ABCD의 연산 횟수로 선택하게 됩니다.

 

결론

결국 이 문제를 푸는 방식은, 2개의 부분문제를 하나로 합쳐나가는 것입니다. Algorithms(S. Dasgupta et al. 2006)에 수록된 다음 그림이 이를 잘 나타내줍니다.

Algorithms(S. Dasgupta et al. 2006) Figure 6.7

dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + lst[j][0]*lst[k][1]*lst[j+i][1])

위 코드는 결국, 이전 단계의 부분문제 2개의 결과와 그 둘을 합치는데 필요한 연산의 총 합을 구한다고 할 수 있습니다. 어떤 문제를 푸는데 도달할 수 있는 길이 여러개라면(k), 모든 경우를 비교해서 가장 optimal한 값을 찾아나간다고 볼 수 있습니다. 이 과정에서 부분문제의 optimal한 결과를 더 큰 부분문제를 풀 때 사용할 수 있으므로 계산 후 2차원 배열에 저장하고, 다음 단계를 풀 때 가져와서 사용하게 되죠.

 

시간복잡도는 O(N^3)입니다. i, j, k를 사용하는 for문 3개가 중첩되어있으니... 각 대각선에 있는 칸을 채워나가면서, 한 칸 채울 때 k번 돌아야 하니 O(N^3)입니다.

 

 

여담으로, 백준의 이 문제는 단 한 명도 Python3을 이용해 맞은 사람이 없습니다. 시간 초과가 나서... PyPy3으로 제출하면 시간 초과 없이 문제를 풀 수 있습니다.

 

*2022년 6월 기준으로 이 문제를 python3을 이용해서 푼 사람들이 조금 있네요. 이걸 어떻게 python3으로 풀지? 하는 분들은 이 블로그를 참고하시길 바랍니다.