[프로그래머스 Level.3] 최적의 행렬 곱셈 (연습문제) (Java)

문제 링크

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

프로그래머스

 

 

 

 

코딩테스트 연습 > 연습문제 > 최적의 행렬 곱셈

 

 

 

문제 설명

 

 

크기가 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이하의 자연수 입니다.
• 계산을 할 수 없는 행렬은 입력으로 주어지지 않습니다.

 

---

 

입출력 예

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

 

 

입출력 예 설명

 

입출력 예#1

문제의 예시와 같습니다.

 

 

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(int[][] matrix_sizes) {
        int answer = 0;
        int[][] dp = new int[matrix_sizes.length][matrix_sizes.length];
        
        for(int i=0; i<matrix_sizes.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
            dp[i][i] = 0;
        }
        
        for(int i=1; i<matrix_sizes.length; i++) {
            for(int start=0; start+i<matrix_sizes.length; start++) {
                int end = start + i; // 마지막 행렬의 위치(인덱스)
                
                // 기준의 위치는 start ~ end 범위 내 ((start~fixed까지 곱한 행렬) * (fixed+1~end까지 곱한 행렬))
                for(int fixed=start; fixed<end; fixed++) { 
                    // matrix_sizes[fixed][1] == matrix_sizes[fixed+1][0]
                    dp[start][end] = Math.min(dp[start][end], dp[start][fixed] + dp[fixed+1][end] + (matrix_sizes[start][0] * matrix_sizes[fixed][1] * matrix_sizes[end][1])); 
                }
            }
        }
        
        answer = dp[0][matrix_sizes.length-1];
        
        return answer;
    }
}

 

풀이

1. 연쇄행렬 최소곱셈 알고리즘이란 행렬들의 곱을 최소의 연산으로 수행하는 최소횟수을 구하는 알고리즘이다.
   행렬의 곱셈에서 결합법칙은 성립하지만 어떤 형태로 결합하느냐에 따라 계산 횟수가 달라질 수 있다.
   만약 행렬의 개수가 5개라면 모든 결합의 마지막 결합 형태는 5 - 1인 4가지로 분류할 수 있다. (행렬의 개수 - 1)
   행렬 A, B, C, D, E 를 곱한다면 (A)(BCDE), (AB)(CDE), (ABC)(DE), (ABCD)(E)로 총 4가지가 된다.
2. 따라서 DP를 이용하여 i행렬부터 j행렬까지의 곱셈을 최소 연산으로 수행하는 횟수를 dp[i][j]에 저장하여 최종적으로 dp[0][matrix_sizes.length-1]을 이용하여 모든 행렬의 곱셈을 최소 연산으로 수행하는 횟수를 구하면 된다.
3. dp[i][j]를 구할 때는 사이 지점(fixed)을 이용하여 i ~ fixed , fixed+1 ~ j를 이용하여 구하도록 한다.
   예를 들어 행렬 A, B, C, D, E 가 있을 때 (AB)(CDE)를 살펴보면 fixed가 B일 때는 AB * CDE 이므로 AB를 곱한 행렬의 최솟값인 dp[A][B] 와 C~E까지 곱한 행렬의 최솟값인 dp[C][E] 에다가 AB 행렬과 CDE 행렬을 곱한 값인 (matrix[A][0] * matrix[C][0] * matrix[E][1])를 더하는 것이다. 따라서 dp[A][E] = dp[A][B] + dp[C][E] + (matrix[A][0] * matrix[C][0] * matrix[E][1])가 된다. (matrix[B][1]과 matrix[C][0]는 같으므로 matrix[C][0]을 matrix[B][1]로 대체 가능하다)
4. 2차원 배열 dp를 생성하고 MAX 값으로 초기화하고 dp[i][j]가  i == j인 경우는 0으로 초기화한다.
5. 이제 3중 for문을 이용하여 dp를 채워나가도록 한다.
6. 우선 첫번 째 for문에서는 행렬 2개를 결합할 때부터 모두 결합할 때까지 1~matrix_sizes.length- 1까지 순회한다. (start에서 start + i 인덱스까지 결합하기 때문에 i + 1개를 결합)
7. 두번 째 for문에서는 start 지점을 0인덱스부터 start + i가 matrix_sizes의 범위를 벗어나지 않을 때까지 순회한다.
   start 인덱스 행렬부터 end(start + i) 인덱스의 행렬까지 결합할 것이다.
8. 이제 start부터 end -1까지에서 기준점(fixed)을 잡고 start ~ fixed까지 결합한 행렬과 fixed+1 ~ end까지 결합한 행렬을 구하고 두 결합한 행렬을 다시 결합하는 곱셈의 최솟값을 구하도록 한다.
9. 이렇게 3중 for문을 돌면서 dp[start][end]를 구하는 것이며 start행렬부터 fixed 행렬까지를 곱한 최소 연산 수행 횟수 dp[start][fixed]와 fixed+1행렬부터 end 행렬까지를 곱한 최소 연산 수행 횟수 dp[fixed+1][end]를 더하고 여기에 두 결합한 행렬을 곱하는 연산 횟수인 (matrix_sizes[start][0] * matrix_sizes[fixed][1] * matrix_sizes[end][1]) 를 더한 다음 기존 dp[start][end]와 비교하여 작은 값을 dp[start][end]에 업데이트 한다.
10. 모든 for문을 돌고 dp 배열을 업데이트 한 후에 최종적으로 모든 행렬을 곱하였을 때 최소 연산 횟수인 dp[0][matrix_sizes.length-1]를 answer에 저장하고 반환한다. 

 

참고

https://source-sc.tistory.com/24 

https://youngyin.tistory.com/155