프로그래머스 [Lv. 3] 최적의 행렬 곱셈 {언어 : JavaScript} [다시 풀어 보기]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12942?language=javascript

프로그래머스

정답 코드

function solution(matrix_sizes) {
    const n = matrix_sizes.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(Infinity));

    // 대각선은 0으로 초기화 (하나의 행렬은 곱할 필요가 없으므로)
    for (let i = 0; i < n; i++) {
        dp[i][i] = 0;
    }

    // 간격을 1부터 n-1까지 늘려가며 최소 곱셈 횟수를 계산
    for (let length = 1; length < n; length++) {
        for (let i = 0; i < n - length; i++) {
            const j = i + length;
            for (let k = i; k < j; k++) {
                dp[i][j] = Math.min(
                    dp[i][j],
                    dp[i][k] + dp[k + 1][j] + matrix_sizes[i][0] * matrix_sizes[k][1] * matrix_sizes[j][1]
                );
            }
        }
    }

    return dp[0][n-1];
}

풀이 방법

 

1. DP 테이블 초기화: dp[i][j]는 i번째 행렬부터 j번째 행렬까지 곱하는 데 필요한 최소 연산 횟수를 나타낸다. dp[i][i]는 0으로 초기화된다.
2. 간격에 따른 최소 곱셈 횟수 계산: length는 현재 비교하는 행렬들의 범위다. 이를 증가시키면서 모든 범위에 대해 최소 곱셈 횟수를 계산한다.
3. 점화식 사용: dp[i][j]는 dp[i][k] + dp[k + 1][j] + matrix_sizes[i][0] * matrix_sizes[k][1] * matrix_sizes[j][1]의 최소값으로 업데이트된다. 여기서 k는 범위를 분할하는 지점이다.
4. 결과 반환: 최종적으로 dp[0][n-1]에는 전체 행렬 곱셈에서 최소 연산 횟수가 저장된다.

 

느낀점

• dp일거라고 생각은 했지만 계산 방법을 떠올리지 못했다.
• 다시 풀어 보고 방식을 터득하자.