[백준 11049] 행렬 곱셈 순서 (Python)

문제

11049번: 행렬 곱셈 순서

크기가 NxM인 행렬 A와 MxK인 B를 곱할 때 필요한 곱셈 연산의 수는 총 NxMxK번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다.

예를 들어, A의 크기가 5x3이고, B의 크기가 3x2, C의 크기가 2x6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자.

• AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5x3x2 + 5x2x6 = 30 + 60 = 90번이다.
• BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3x2x6 + 5x3x6 = 36 + 90 = 126번이다.

같은 곱셈이지만, 곱셈을 하는 순서에 따라서 곱셈 연산의 수가 달라진다.

행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력으로 주어진 행렬의 순서를 바꾸면 안 된다.

먼저 완전 탐색으로 문제 접근하기

모든 행렬 곱셈의 순서를 시도해볼 수 있을까?

동적 계획법을 이용하기에 앞서 문제를 완전 탐색 알고리즘으로 해결하는 방법을 떠올려보자.

완전 탐색 알고리즘을 이용한다면 주어진 행렬을 어떤 순서로 곱할 때 연산의 횟수를 최소화할 수 있는지 알아보기 위해 N개의 행렬을 곱하는 모든 순서를 시도해볼 수 있을 것이다.

def solution(n, array):
    if n == 1: # 기저 사례 - 1개의 행렬이 될 때까지 행렬의 곱셈을 지속하였다.
        return 0

    answer = 1e9

    for i in range(len(array) - 1):
        ax, ay = array[i]
        _, by = array[i + 1]
        op = ax * ay * by
        s = op + solution(n - 1, array[:i] + [[ax, by]] + array[i + 2:])
        if s < answer:
            answer = s
    return answer

완전탐색을 통해 모든 순서의 곱셈을 시도하는 코드를 작성하였다.

solution 함수는 행렬의 크기를 담는 리스트(array)와 그 길이(n)를 인자로 받아 최소 곱셈 연산의 수를 반환한다.

인자로 주어진 리스트 중 인접한 두 행렬을 골라 곱한 후 재구성한 행렬의 크기 리스트를 인자로 넘겨 재귀 호출한다.

재귀 함수의 실행 결과를 이용하여 계산한 연산 횟수 중 최솟값을 채택하므로 행렬 곱셈의 중간 상태(array 인자로 넘어온 리스트)에 대해 앞으로의 경우의 수 중 가장 적은 연산 횟수를 보장한다.

이대로 동적계획법 적용하기

현재 인자값에 대해 메모이제이션을 사용할 수 있을까?

앞서 함수의 재귀 호출을 활용하여 Top-Down 방식으로 행렬 곱셈 연산의 최솟값을 구해보았다. 그런데 매번 함수가 실행될 때마다 현재 상태에서 곱할 수 있는 모든 인접한 행렬에 대해 반복적으로 재귀 호출하므로 함수 호출의 횟수가 증가하고 같은 인자를 받아 실행하는 경우가 중복되기도 한다.

완전 탐색에서 동적 계획법으로 개선하기 위해 같은 인자에 대한 함수 호출 결과를 캐싱하여 중복된 재귀 호출이 일어나는 것을 방지할 수 있다. 그런데 현재의 solution 함수 그대로 인자별 반환 값을 캐싱할 수 있을까?

현재 solution 함수는 리스트형 자료를 인자(array)로 받고 있다. 임의의 인접한 두 행렬을 곱한 뒤의 전체 행렬 array를 인자로 받는데 함수를 실행할 때마다 array를 인자로 받는 것은 메모리를 과도하게 사용하게 될뿐더러 인자로 넘겨받은 array는 재사용되는 빈도가 낮고 그 가짓수가 많다.

더 효율적으로 결과를 저장, 재사용할 수 있도록 array 인자를 더 효율적인 형태로 변환하여보자.

함수 인자 변환하기

현재의 인자값이 꼭 필요한 정보를 가지고 있는가?

배열을 인자로 넘기지 않고 다른 값으로 부분 문제를 표현할 수 있을까?

array 인자를 저장에 쉽게끔 변환하기 위해 먼저 넘겨받은 array가 함수 내 연산에 꼭 필요한 정보인지를 따져보자.

앞서 완전탐색 알고리즘의 사고방식으로 생각하자면 두 행렬을 곱한 뒤의 행렬 리스트를 인자로 넘겨주어야 재귀호출된 후 해당 값을 이용해 행렬 곱셈에 이용할 수 있다고 생각할 수 있다.

하지만 처음 N개 행렬의 목록을 놓고 생각해보자. N 개 행렬의 리스트 내 특정 구간에서의 행렬 곱셈 연산 횟수를 최소화하는 곱셈의 순서는 유일하다. 이와 같은 사실로 말미암아 N개 행렬 리스트 내에서 구간을 특정할 수 있다면 구간 내 곱셈 연산을 최소화하는 곱셈의 순서를 특정할 수 있음을 알 수 있다.

부분 문제 다시 정의하기

앞서 행렬 리스트 중 특정 구간에 대해 행렬 연산 횟수의 최적해를 유일함을 알아보았다. 이것을 부분 문제의 정의로 바꾸면 다음과 같다.

solution(start, end) = array 리스트 내 start부터 end까지의 구간 곱셈 연산의 최솟값

문제의 설명과 같이 크기가 NxM인 행렬 A와 MxK인 B를 곱할 때 필요한 곱셈 연산의 수는 총 NxMxK번이다. 그런데 행렬 리스트 내 특정 구간을 어떤 순서로든 곱한 행렬의 크기는 구간 내 첫번째 요소의 행과 마지막 요소의 열 값과 같음을 주목하자. 이와 같은 성질을 이용하면 행렬을 곱한 결과에 대해 행렬 리스트를 재구성하지 않고도 결과 행렬의 크기를 알 수 있으며 곱셈 연산의 수를 계산하는 데에 활용할 수 있다.

결과적으로, 주어진 리스트를 두 구간으로 나누어 이 두 구간을 곱하는 연산의 수를 계산하고, 양 구간의 연산의 수를 각각 재귀적으로 계산해 더하는 식으로 연산의 수를 계산할 수 있다.

정답 코드

import sys

def solution(start, end): # s: 구간 내 첫번째 요소의 인덱스, e: 구간 내 마지막 요소의 인덱스
    if end == start:
        return 0

    if dp[start][end] != -1:
        return dp[start][end]

    answer = 1e9
    for i in range(start+1, end+1):
        ax, _ = array[start]
        bx, _ = array[i]
        _, cy = array[end]
        op = ax * bx * cy
        sum = op + solution(start, i-1) + solution(i, end)
        if sum < answer:
            answer = sum

    dp[start][end] = answer

    return answer

n = int(sys.stdin.readline())
array = [[int(i) for i in sys.stdin.readline().rstrip().split()] for _ in range(n)]
dp = [[-1 for _ in range(n)] for _ in range(n)]

print(solution(0, n-1))

위에서 정의한 부분 문제를 구현한 정답 코드이다. solution 함수는 행렬 크기 리스트의 시작 인덱스와 끝 인덱스를 인자로 받아 리스트를 임의의 두 구간으로 나눈다. 그리고 이 두 구간에 대해 각각 곱한 행렬을 곱하는데 필요한 연산의 수 op 값을 계산하고 두 구간 각각의 최소 연산 횟수값을 재귀적으로 계산해 더해준다. 결과적으로 리스트 내 임의의 두 구간에 대해 계산한 값중 가장 적은 값을 반환한다.

메모이제이션에는 크기가 N인 배열의 인덱스인 s와 e 두 변수를 담기 위해 NxN 크기의 배열을 이용하여 각각의 리스트 시작점, 끝점에서의 최소 연산 횟수를 캐싱하였다.