Programmers LV.3 최적의 행렬 곱셈

Programmers LV. 3 최적의 행렬 곱셈

문제

크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다.
예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 = 30번의 곱하기 연산을 해야 합니다.

행렬이 2개일 때는 연산 횟수가 일정 하지만, 행렬의 개수가 3개 이상일 때는 연산의 순서에 따라서 곱하기 연산의 횟수가 바뀔 수 있습니다. 예를 들어서 크기가 5 by 3인 행렬 A, 크기가 3 by 10인 행렬 B, 크기가 10 by 6인 행렬 C가 있을 때, 순서대로 A와 B를 먼저 곱하고, 그 결과에 C를 곱하면 A와 B행렬을 곱할 때 150번을, AB 에 C를 곱할 때 300번을 연산을 해서 총 450번의 곱하기 연산을 합니다. 하지만, B와 C를 먼저 곱한 다음 A 와 BC를 곱하면 180 + 90 = 270번 만에 연산이 끝납니다.

각 행렬의 크기 matrix_sizes 가 매개변수로 주어 질 때, 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수를 return하는 solution 함수를 완성해 주세요.

제한 사항

• 행렬의 개수는 3이상 200이하의 자연수입니다.
• 각 행렬의 행과 열의 크기는 200이하의 자연수 입니다.
• 계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.

문제 설명

처음 문제를 접하고 어떻게 접근해야 할지 1시간은 고민한 것 같다. 이후 여러 방법을 사용하여 문제를 풀고자 했지만 4시간이 넘도록 문제를 풀 수가 없었다. 그래서 문제 접근법을 알고자 질문하기에 들어가 전현서 님의 문제 해설을 보았다. 정말 잘 정리되어 있어서 해설을 보고 난 이후 문제를 바로 풀 수 있었고, 다이나믹 프로그래밍의 정의를 다시 한 번 상기할 수 있었다.

1. N by M 행렬과 M by K 행렬을 곱하면 N by K 행렬을 결과값으로 반환한다. 또한 연산 횟수는 N M K 가 된다.
2. 행렬은 결합법칙은 성립하지만, 교환법칙은 성립하지 않는다.

1번 규칙에 의해서 두 행렬을 곱하면, 두 행렬 사이에 끼어있는 중간에 같은 숫자가 날라가는 사실을 알고있다.
그래서 "해당 부분을 어떻게든 모종의 순서대로 잘 날려보내면, 최적의 행렬 곱셈을 할 수 있지 않을까?"라고 생각할 수 있다.
그런데, 행렬곱을 잘만 생각해보면, 모든 행렬이 곱해져 하나의 행렬이 남을 때까지. 끝없은 곱의 연속이다.
과연, 가운데 값만 잘 제거한다고 행렬의 곱셈 연산 횟수가 낮아질까? 잘만 생각해도 아니지 않은가?
행렬 곱의 최소 곱 연산 횟수에 영향을 주는 요인은 단순히 가운데의 공통 값이 아니다. N x M x K 가 연산 횟수 결과인만큼.
즉, 모든 행렬의 요인이 서로서로 곱셈 연산 횟수에 영향을 끼친다.
그렇다. 해당 문제는 모든 경우를 파악해서 정답을 도출해내는 문제이다.

그럼, 모든 경우를 계산하려면, 어떻게 하는가?
간단하다. 2개씩 곱한 최소 연산 횟수, 3개씩 곱한 최소 연산 횟수, .... , n개씩 곱한 최소 횟수를 각각 구해보면, 마지막에 구하는 것이 결과가 되지 않겠는가?

예시를 하나 들어보자.
[4, 5], [5, 10] [10, 7], [7, 3]
예시에도 알 수 있는 인접한 두 행렬은 연결된 사이즈가 항상 같다는 것을 알 수 있다.
두 행렬을 곱해서 새로운 행렬이 나와도 그 법칙은 성립한다. 한 번 해보면 알 수 있다.

여기서 [4, 5] ~ [7, 3]을 모두 곱하려면 4개의 행렬을 곱한 최소 연산 횟수를 알아야 한다. 한 번 구해보자.

case1) 자기자신을 곱한경우.

• 곱할 것이 없다는 것을 알 수 있다. 자신 자신은 곱할 수 없으므로 최소 연산 횟수는 0이다.

case2) 인접한 행렬들의 곱. (2개의 행렬을 곱한 경우.)

• 인접한 행렬들을 각각 곱한다면, 그것보다 더 작은 최소연산 횟수는 그보다 더 작은 것이 불가능하다.
• 행렬의 교환법칙은 성립하지 않으므로, 두 행렬 간의 곱의 연산 방법은 하나 밖에 존재하지 않기 때문이다.

case3) 2칸 떨어진 행렬들의 곱. (3개의 행렬을 곱한 경우.)

• 인접한 행렬의 계산은 하나밖에 없지만, 3개 행렬의 연산은 결합법칙이 성립하여 1, 2, 3번 행렬이 존재한다면, (1, 2), 3 과 또는 1, (2, 3) 과 같이 묶어서 연산이 가능하다. 우리는 (1, 2)와 (2, 3)의 연산 결과를 case2에서 구했으므로, 비교하여 어떤 값이 더 작은지 알 수 있을 것이다. 이런 연산을 모든 경우의 수에 대해 하면 된다.

case4) 3칸 떨어진 행렬들의 곱. (4개의 행렬을 곱한 경우. 정답을 구하는 연산)

• 4개의 행렬의 곱을 구하는 것은 답을 구하는 것이다. 4개의 행렬도 마찬가지의 곱이 성립한다. 1, 2, 3, 4의 행렬이 존재한다면, 1, (2, 3, 4) 와 (1, 2, 3), 4 두 가지의 연산이 성립한다. 그런데 우리는 case3에 대해서, 3가지의 행렬들에 대한 곱에 대한 최소 연산 결과를 알고 있다. 마찬가지로 대입해서, 더 작은 값이 우리가 원하는 답이 된다.

위의 간단한 예시로 어느정도 이해가 가능했으면 좋겠다.
행렬을 곱하는 갯수를 0개 부터 N개 까지 순차적으로 늘려 최소 곱 연산 횟수를 구하는 방식이다.
메모리 낭비를 방지하기 위해 DP를 사용한 연산이라고 봐도 좋다.
우리가 무조건 아는 수부터 연산하고 한단계씩 경우의 수를 늘리면서 연산을 한다.

우린 여기에서 2차원 배열인 DP를 선언한다.
DP = [[0 for i in range(len(matrix_sizes))] for j in range(len(matrix_sizes))]

위와 같이 간단히 파이썬 코드로 나타 낼 수 있을 것이다.

임의의 변수 a, b가 존재할 때, (a <= b 인 경우만)
DP[a][b] 의 의미는 a부터 b까지의 곱의 최소 연산 횟수가 된다.

만약 문제에서 제시한 matrix_sizes의 수가 4개일 경우(1, 2, 3, 4 행렬), 어떤식으로 값이 구해지는지 보자.

case1) 1개의 행렬을 곱하는 경우.

• 아무 연산이 필요가 없다. 만약 python코드를 사용하지 않았다면,
  DP[a][b] = 0 과 같은 연산을 수행하여 초기값을 셋팅해줄 수도 있다.

case2) 2개의 행렬을 곱하는 경우.

• (1, 2), (2, 3), (3, 4)의 행렬 연산을 수행한다. DP에 각각 최소 연산값을 계산한다. for문 돌려서 어떻게 a, b를 만들고 해당 원소에 접근 할 수 있을지 생각해본다.

case3) 3개의 행렬을 곱하는 경우.

• (1, (2, 3)), ((1, 2), 3), (2, (3, 4)), ((2, 3), 4)와 같이 행렬 연산을 수행한다. 여기서 부터는 괄호 안에 2개씩 묶인 값을 알고 있을 것이다. 해당 값을 이용해서 계산을 수행 할 수 있어야한다. 또한 (1, 2, 3) 과 (2, 3, 4)에 대해 괄호를 두 번씩 묶어서 연산하는 것을 알 수 있다. 여기서 제3의 for문이 필요하다는 사실을 유추해낼 수 있다.

case4) 4개의 행렬을 곱하는 경우.

• (1, (2, 3, 4)), ((1, 2), (3, 4)), ((1, 2, 3), 4) 와 같이 계산한다. 괄호에 묶어있던 값은 case2 ~ case3에서 계산했던 값이므로 충분히 알 수 있을 것이다.

여기서 이 모든걸 한 번에 해결해주는 점화식을 알려주겠다.
matrix_sizes를 m이라고 약칭함.

DP[a][b] = min(DP[a][b], DP[a][k] + DP[k+1][b] + (m[a][0] * m[k][1] * m[b][1]))

DP[a][b]를 구하려면 DP[a][b]와 DP[a][k] + DP[k+1][b] + (m[a][0] * m[k][1] * m[b][1]) 와 비교하여 작은 값을 구하면 된다.
여기서 a와 b가 아닌 k가 나온다. k는 a ~ (b-1)까지를 for문으로 돌리는 변수다.
a에서 b구간을 1씩 늘리면서 돌리는 것이다.
DP[a][k] + DP[k+1][b] 는 a에서 k까지의 최소 곱 연산과 k+1 부터 b까지의 최소 곱 연산을 더한 것이다.
그리고 여기다가 이 최소 곱연산을 한 결과를 합치려면 k로 중간에 짤려진 부분부터 곱연산을 수행하여 다시 새로 더해주어야한다.

이해하는가? m by n 과 n by k를 연산하면 m by k가되는 것을 이용하여, 위와 같은 연산이 가능해진다.

k의 역할은 두 행렬 곱사이에 중간에 하나씩 잘라다가 결합법칙을 만들어준다.
(1, (2, 3)) 연산을 이와 같이 할 경우는 k가 0일 경우.
((1, 2), 3) 이와 같이 할 경우는 k가 1인 경우이다.

즉, k를 하나씩 늘려가며 결합을 묶어서 최소 연산 횟수를 찾아내는 방식이다.

여기서 주의할 점은 처음 값이 0으로 지정되어 있으므로 DP[a][b]를 연산할 경우
초기 값으로, 충분히 크게 주고 연산을 시작해야한다.

마지막으로 전체적인 for문의 구조를 보여겠다.
n은 matrix_size의 길이라고 한다.

최상단 for문 몇개의 행렬을 계산할지 정하는 변수이다. 즉, 곱할 두 행렬간의 간격이다.

for dist in range(1, L):  # dist는 곱할 두 행렬간의 간격
	for start in range(L - dist):  # start는 행렬곱의 시작 행렬
    	a = start
        b = start + dist
        for k in range(a, b):

정답 코드

import sys
  
def solution(matrix_sizes):
    answer = 0
    L = len(matrix_sizes)
    dp = [[0 for _ in range(L)] for _ in range(L)]
    
    for dist in range(1, L):  # dist는 곱할 두 행렬간의 간격
        for start in range(L - dist):  # start는 행렬곱의 시작 행렬
            a = start
            b = start + dist
            dp[a][b] = sys.maxsize
            for k in range(a, b):
                middle_product = matrix_sizes[a][0] * matrix_sizes[k][1] * matrix_sizes[b][1]
                dp[a][b] = min(dp[a][b], dp[a][k] + middle_product + dp[k + 1][b])
    return dp[0][-1]