[백준 11049번] 행렬 곱셈 순서 (C++, Python)

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

이번 포스트에서는 백준 알고리즘 문제인 행렬 곱셈 순서를 포스팅 하도록 하겠습니다.

 

해당 문제는 solved.ac 기준 골드 3에 위치한 문제입니다.

 

먼저 문제입니다.

행렬의 개수 N과 각 행렬의 크기인 r과 c가 주어집니다. 이때, 이 행렬들을 곱하는데 필요한 곱셈 연산의 최소값을 찾아서 출력하는 문제입니다.

 

해당 문제를 브루트포스 알고리즘으로 풀게 되면, 앞에서 구했던 최소 연산 횟수를 다시 계산해야하는 일이 일어납니다. N이 500까지 주어지고 시간제한이 1초이기 때문에 O(N^3) 인 행렬 곱셈을 브루트포스로 해결하게 되면 비효율적입니다.

 

따라서, 연쇄 행렬 곱셈을 이용한 DP 알고리즘으로 문제를 해결합니다.

 

해당문제는 선형 DP배열이 아닌, 2차원 DP 배열을 사용합니다.

 

3
5 3
3 2
2 6

예제로 주어진 입력을 예시로 하였을 때, 5*3 행렬 A와 3*2 행렬 B, 2*6 행렬 C가있습니다.

먼저 행렬 A와 행렬 B를 곱하면 행렬 곱셈 횟수는 5 * 3 * 2 로 30회 입니다. 그럼 곱해서 만들어진 행렬 X는 5*2의 행렬 이므로, 행렬 C와 곱해집니다. 그럼 곱셈 횟수는 30 + 5 * 2 * 6 입니다. 따라서, 해당 행렬 A,B,C의 곱셈 횟수는 90회가 됩니다.

 

하지만, 행렬은 곱셈 순서를 바꿀 수 있기 때문에, 행렬 B와 C를 먼저 곱할 수 있습니다. 그럼 행렬 곱셈 횟수는 3 * 2 *6 으로 36회 입니다. 그럼 곱해서 만들어진 행렬 Y는 3*6 행렬 이므로 행렬 A와 곱해집니다. 그럼 곱셈 횟수는 36 + 5 * 3 * 6 입니다. 따라서, 행렬 A,B,C의 곱셈 횟수는 126회 입니다.

 

위처럼 순서를 바꿈에 따라 곱셈 횟수가 달라지기 때문에 이를 고려하여 점화식을 구성해야 합니다.

 

행렬 A와 B를 곱하는 예시 부터 시작하여 올라가면, 이때 곱셈 횟수는 행렬 A를 만드는데 드는 연산 횟수 + 행렬 B를 만드는데 드는 연산 횟수 + A와 B를 곱하는데 드는 연산 횟수입니다. 

 

이를 일반화 하면 DP[k][j] + DP[j + 1][end] + matrix[k][0] * matrix[j][1] * matrix[end][1] 입니다. (각 변수에 대해서는 뒤에서 코드와 함께 설명하겠습니다.) 

 

위 식에서 DP[k][j]가 행렬 A를 만드는데 필요한 최소 연산 횟수, DP[j + 1]이 행렬 B를 만드는데 필요한 최소 연산 횟수,

matrix[k][0] * matrix[j][1] * matrix[end][1]이 행렬 A와 B를 곱하는 연산 횟수가 됩니다.

 

다음의 C++ 코드를 참고하여 다시 보겠습니다.

 

#include <iostream>
 
using namespace std;
 
int main() {
    int n;
    cin >> n;
    
    int matrix[n][2], dp[n][n] = {0,};
    for(int i = 0; i < n; i++)
        cin >> matrix[i][0] >> matrix[i][1];
 
    for(int i = 1; i < n; i++) {
        for(int k = 0; k + i < n; k++) {
            int end = k + i;
            dp[k][end] = 1e9;
            
            for(int j = k; j < end; j++) {
                int last = matrix[k][0] * matrix[j][1] * matrix[end][1];
                int front = dp[k][j] + dp[j + 1][end] + last;
                dp[k][end] = min(dp[k][end], front);
            }
        }
    }
    cout << dp[0][n - 1];
    return 0;
}

위 식에서 i는 행렬의 대각 부분을 의미하고, k는 행렬의 행, end는 현재 값을 넣어야할 열, j는 end 까지의 인덱스를 가리킵니다.

따라서, i가 진행함에 따라, 위 이미지에서 상삼각행렬 부분을 채워줍니다. i가 1부터 시작인 이유는 2차원 dp 배열을 0으로 초기화 하였기 때문에, 자기자신의 곱은 0이므로 i가 1부터 시작합니다.

 

그 다음 반복문에서 k는 0부터 시작하여 k+i 가 n보다 작을 때 까지 합니다. k+i는 현재 i값에서 대각으로 내려가야할 값을 가리키기 때문에 현재 대각을 다 채울때 까지 반복합니다. 그러므로 end 또한 k+i로 채워야할 값을 가리키고 반복때마다 다시 세팅됩니다.

 

다음 반복문에서는 행렬을 곱하고, 연산횟수를 구하는 부분으로 먼저 last에 적히는 식인

matrix[k][0] * matrix[j][1] * matrix[end][1]는 j가 k부터 시작하기 때문에, 초반 두 곱은 한 행렬의 a,b 값이고, end가 구하고자 하는 위치의 행이기 때문에 b*c 중 c를 선택합니다.

 

그리고, front에 있는 dp[k][j] + dp[j + 1][end] 로 이전에 구해뒀던 최소연산횟수를 더해줍니다.

 

결국 마지막에 모든 행렬의 최소연산횟수는 dp[0][n-1] 에 저장되므로 이를 출력하면 끝입니다.

 

아래는 Python 코드입니다.

 

n = int(input())
matrix[list(map(int, input().split())) for _ in range(n)]
dp = [[0] * for _ in range(n)]
 
for i in range(1, n) :
    for k in range(0, n) :
        if k + i >= n :
            break
        end = i + k
        dp[k][end] = 2**31
        for j in range(k, end) :
            dp[k][end] = min(dp[k][end], dp[k][j] + dp[j + 1][end] + matrix[k][0] * matrix[j][1] * matrix[end][1])
print(dp[0][n - 1])

필자는 해당 문제의 이론은 이해하는데 어려움이 적었으나 점화식을 구성하는데 있어서, i와 k, j, end가 가리키는 바를 알지 못해서 이해하는데 어려웠습니다. 그래서 설명을 최대한 해보았으나, 이해와 설명은 확실히 조금 다른 레벨인 것 같다고 느끼는거 같네요..

 

이론은 ABCD의 행렬 곱을 할때 행렬곱은 A(BCD), (AB)(CD), (ABC)D 등의 순서로 구해지고 또 이안에서

A((BC)D), A(B(CD)) 등으로 나누어 지기 때문에 DP의 핵심인 메모이제이션을 이용해 AB, CD, BC 등의 연산 횟수를 미리 계산 해두고 저기서 다시 행렬을 곱하는 경우의 수 중에서 최소값만을 선택하면 끝에 ABCD 행렬 곱의 최소 연산 횟수가 저장됩니다.

 

저보다 똑똑하신 분들이 많기 때문에, 아마 저보다 빨리 이해하실거라 생각합니다.

추가로 위의 Python 코드를 Python3 으로 제출하게 되면 시간 초과가 걸립니다. 저는 아직 저걸 해결하지 못해서 PyPy3 로 제출하여 해결했습니다.

 

다음 포스트에서 다른 백준 알고리즘 문제로 포스팅 하겠습니다. 감사합니다.