[programmers] 최적의 행렬 곱셈

https://school.programmers.co.kr/learn/courses/30/lessons/12942

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

완전탐색(dfs) + dp(memoization)

 

---------------------------------------------------풀이----------------------------------------------------

 

행렬이 AxBxCxDxE라고 생각해보자.

그러면 케이스는

(A)x(BxCxDxE)

(AxB)x(CxDxE)

(AxBxC)x(DxE)

(AxBxCxD)x(E)

로 나눌 수 있다.

즉, 두 개로 나누어서 분할할 수 있는 것이다.

(A)x(BxCxDxE)이 첫 번째 케이스를 다시 생각해보자.

좌측의 A는 계산하기 위해 필요한 곱셈이 0이다.

우측의 BxCxDxE는 다시 다음과 같이 나눌 수 있다.

(B)x(CxDxE)

(BxC)x(DxE)

(BxCxD)x(E)

여기서 첫 번째 케이스를 다시 분할하면,

좌측의 B는 곱셈이 0번,

우측의 CxDxE는 다시 다음과 같이 나뉜다.

(C)x(DxE)

(CxD)x(E)

이런식으로, 계속해서 분할해 나가면서 최솟값을 구하면 되는 문제이다.

 

따라서, 이분할에서 이름을 따서 함수를 bs()라고 지었고, 체크할 matrix_sizes에서의 인덱스 시작점 s, 끝점 e를 매개변수로 주었다.

인덱스 s부터 e까지를 두 부분으로 나누기 위해,

i를 s+1부터 e까지 돌면서, [s,i-1]까지를 왼쪽 부분, [i,e]까지를 오른쪽 부분으로 두고 행렬의 곱을 계산했을 때의 최솟값을 구했다.

 

[s,e]에서의 행렬 곱의 최소 횟수 = 왼쪽 부분에서의 최소 + 오른쪽 부분에서의 최소 + 왼쪽에서 계산된 행렬과 오른쪽에서 계산된 행렬을 곱할 때의 횟수

 

왼쪽 부분에서의 최소 = bs(s, i-1)

오른쪽 부분에서의 최소 = bs(i, e)

왼쪽에서 계산된 행렬과 오른쪽에서 계산된 행렬을 곱할 때의 횟수 = (matrix[s][0] by matrix[i-1][1]) x (matrix[i][0] by matrix[e][1]) 두 행렬 곱에서의 횟수 = matrix[s][0] x matrix[i][0] x matrix[e][1] 이다.

따라서, 전체 계산은

bs(s, i-1) + bs(i, e) + matrixes[s][0] * matrixes[i][0] * matrixes[e][1];

로 나타낼 수 있다.

 

이렇게만 하면, 시간 초과에 걸리게 된다.

따라서, dp의 memoization 기법을 적용하였다.

즉, 기존에 계산한 최소 값을 미리 저장해두고, 다음에 재사용하는 것이다.

이 값을 mins[][] 배열에 저장하였다.

mins[s][e] = s번째 행렬부터 e번째 행렬까지의 곱을 할 경우 최소 횟수.

 

이걸 모두 적용한 코드는 다음과 같다.

시작 인덱스(s)와 끝 인덱스(e)가 동일하면 추가적인 곱이 필요 없으므로 0을 리턴하고,

mins[s][e]가 0보다 크면, 이미 계산되어 저장된 값이 있다는 것이므로 그 값을 리턴한다.

없으면, s부터 e까지를 두 부분으로 나누어 최소를 계산하면서 최소인 값을 mins[s][e]에 저장하고 리턴한다.

#include <string>
#include <vector>
#include <climits>

using namespace std;

vector<vector<int>> matrixes;
int mins[200][200] = {0, }; // 행렬의 [s, e]에서의 최소 곱 저장

int bs(int s, int e){
    if(s == e){
        return 0;
    }
    else if(mins[s][e] > 0){
        // 이미 저장된 값이 있으면 리턴
        return mins[s][e];
    }
    
    int cur_min = INT_MAX;
    // i 이전과 i를 포함한 뒷부분으로 나누어 계산
    for(int i = s+1; i <= e; i++){
        // 왼쪽 계산, 오른쪽 계산, 계산된 두 개를 곱한값
        int tmp = bs(s, i-1) + bs(i, e) + 
            matrixes[s][0] * matrixes[i][0] * matrixes[e][1];
        if(tmp < cur_min){
            cur_min = tmp;
        }
    }
    return (mins[s][e] = cur_min);
}

// (a x b) x (b x c) = (a x b x c)
// 각 행렬의 크기 matrix_sizes
// 모든 행렬을 곱하기 위한 최소 곱셈 연산의 수=?
// 계속 둘로 나눠가면서 최종적으로 최소인 값을 리턴
int solution(vector<vector<int>> matrix_sizes) {
    matrixes = matrix_sizes;
    return bs(0, matrixes.size()-1);
}

 

---------------------------------------------------후기----------------------------------------------------

 

오랜만에 알고리즘 문제를 풀어보는거라 걱정했는데, 나름 빠르게 잘 푼 것 같다!

생각보다 전체 다 계산하면 되는 문제라 간단..