프로그래머스 - 최적의 행렬 곱셈 [연습문제

문제 설명:

크기가 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 함수를 완성해 주세요.

---

문제 예시:

matrix_sizes	result
[[5, 3], [3, 10], [10, 6]]	270

---

문제 해결:

def solution(matrix_sizes):
    n = len(matrix_sizes)
    dp = [[0]*len(matrix_sizes) for _ in matrix_sizes]
    
    for idx in range(1, n):
        for idx2 in range(n-idx):
            idx3 = idx2 + idx
            dp[idx2][idx3] = float('inf')
            
            for k in range(idx2, idx3):
                dp[idx2][idx3] = min(dp[idx2][idx3], \
                                     dp[idx2][k] + dp[k+1][idx3] + \
                                     matrix_sizes[idx2][0]*matrix_sizes[k][1]*matrix_sizes[idx3][1])
    return dp[0][n-1]

이번 문제는 내 힘으로 풀 수 없어서 질문들을 참조하였다.

 

문제 설명은 다음과 같다.

DP문제 인데 분할 정복 알고리즘을 수학적으로 생각해 보자

 

전제 조건은 "list 안에서 주는 size는 선형적으로 곱셈이 가능하다"

이 말은 즉슨 idx = 0과 idx = 1의 matrix는 확정적으로 곱셈이 가능하다 이다.

이 조건이 성립하지 않으면 모든 matrix의 경우의 수를 돌아야 한다.. (있었으면 한다 진짜)

 

1. idx는 1부터 n까지 돈다 (Step이라고 생각하면 편함)

2. idx2는 0부터 n-idx까지 돈다 (맨 마지막은 n-idx부터 step (idx)까지 가는 것이기 때문)

3. 이후 Step을 적용한 idx3 = idx2 + idx를 설정한다

4. min값을 찾아야 하므로 최댓값 설정을 inf로 한다

5. 중간에 idx2부터 idx3까지의 최솟값을 구하기 위한 k를 설정한다 (이 말은 즉슨 k는 idx2부터 idx3 사이를 돈다)

6. dp [idx2][idx3]의 min값을 찾기 위해 두 가지를 비교한다

 

첫 번째, 본인

두 번째, k를 들러서 오는 최솟값 = dp [idx2][k] + dp [k+1][idx3] + matrix_sizes [idx2][1]*matrix_sizes [k][1]*matrix_sizes [idx3][1]

이때, 뒤의 " matrix_sizes [idx2][1]*matrix_sizes [k][1]*matrix_sizes [idx3][1]"는 중간에 들러서 곱했을 때 나오는 값이다.

그리고 dp [idx2][k]의 경우 idx2부터 k까지의 최솟값 (step 상관없이)이고 dp [k+1][idx3] 또한 마찬가지로 최솟값이다.

 

이 둘을 비교하여 최솟값을 할당한다.

 

dp는 그려보면 다음과 같다.

 

이해가 되길 바라며 dp를 직접 그려보며 한 줄씩 따라가 보는 것을 추천한다.