[Algorithm] (Java) 연쇄행렬 최소곱셈 알고리즘

연쇄행렬 최소곱셈 알고리즘 (Matrix Chain Multiplication)

주어진 행렬들의 곱을 최소의 연산으로 수행하는 최소횟수를 구하는 알고리즘이다.

행렬의 곱셈에서 결합법칙은 성립하나 순서에 따라서 계산 횟수가 달라질 수 있다. 아래와 같은 행렬로 확인해보도록 하자.

 

그림을 확인해보면 순서에 따라 전체 연산횟수가 달라짐을 알 수 있다.

 

위와 같이 행렬의 개수가 5개일때 모든 결합의 마지막 결합 형태는 다음과 같이 네 가지로 분류가 가능하다. (행렬의 개수가 n 이면 n - 1 가지로 분류가 가능하다.)

(AB)(C(DE)) 는 결국 (AB)(CDE) 와 같고

(A(B(CD)))E 는 결국 (ABCD)E 와 같다.

 

다시 말하자면 행렬의 개수가 n 이면

최소 연산 횟수는 n - 1 가지 경우 중의 최솟값을 구하면 되는 작업이 된다.

 

이를 구할때 DP 로 구할 수 있다.

DP[i][j] = i 번째 행렬부터 j 번째 행렬까지 최소 연산 횟수

i 번째에 n by m 행렬을 matrix[i][0] = n, matrix[i][1] = m

DP[i][j] = min(DP[i][j], DP[i][k] + DP[k+1][j] + matrix[i][0] * matrix[k][1] * matrix[j][1]) (i <= k < j)

가 된다. 

 

프로그래머스

이를 활용한 문제이다. 

 

Code

class Solution {
    public int solution(int[][] matrix_sizes) {
        int length = matrix_sizes.length;
        int[][] dp = new int[length][length];
        
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length - i; j++) {
                int a = j;
                int b = j + i;
                
                if (a == b) dp[a][b] = 0;
                
                for (int k = a; k < b; k++) {
                    dp[a][b] = min(dp[a][b], dp[a][k] + dp[k + 1][b] + matrix_sizes[a][0] * matrix_sizes[k][1] * matrix_sizes[b][1]);    
                }
            }
        }
        
        return dp[0][length - 1];
    }
    
    int min(int a, int b) {
        return a < b ? a : b;
    }
}