(javascript) 최적의 행렬 곱셈

코딩테스트 연습 - 최적의 행렬 곱셈 | 프로그래머스 스쿨

프로그래머스

처음에 떠오른 풀이는 간단했다.

[N, K] 행렬과 [K, M] 행렬을 곱하면 N * K * M번의 곱셈을 수행하고 [N, M] 행렬이 남는다.

이 과정을 보면 중간에 있는 K가 사라지는 것을 알 수 있다.

따라서 모든 행렬의 행과 열의 크기 중에 가장 큰 숫자부터 없애다보면 전체 곱셈의 횟수가 최소가 될거라는 생각이었다.

 

그래서 모든 행렬의 행과 열의 크기 중 가장 큰 숫자를 찾은 뒤, 그 숫자를 없애도록 곱셈을 수행하는 과정을 반복했다.

그러나 결과는 처참했다. 아무래도 풀이 자체가 틀린 모양이었다.

 

결국 찾아낸 해법은 직전에 풀었던 "사칙연산" 문제와 비슷한 방법이었다.

i번째 행렬부터 j번째 행렬까지 정답을 구하려면, i와 j행렬 사이에 있는 임의의 k번째 행렬을 정한 뒤, [i, k]의 정답 + [k+1, j]의 정답 + i[0] * k[1] * j[1] 을 계산하면 된다.

 

예를들어 다섯개의 행렬 ABCDE에서 정답을 구하려면, 가지 경우에서 가장 작은 값을 구하면 된다.

1. A * BCDE

2. AB * CDE

3. ABC * DE

4. ABCD * E

 

1. A * BCDE에서 BCDE를 다시 재귀적으로 풀면 최종 결과를 얻어낼 수 있다.

재귀에서 기저조건은 i = j인 경우, 즉 행렬이 하나밖에 없는 경우이다. 이 때는 필요한 곱셈의 수가 0이다.

 

그러나 단순히 재귀로만 풀면 메모리 낭비 시간 낭비가 발생한다. 위의 예시에서 1, 2, 3, 4 경우를 모두 비교해야하는데, 그 과정에서 중복되는 결과가 너무 많다.

따라서 DP를 적용해서 결과를 저장한다.

 

코드

function solution(matrix_sizes) {
    var answer = 0;
    var dp = Array.from({ length: 200 }, () => Array(200).fill(0));
    const foo = (start, end) => {
        if (start === end) {
            return 0;
        }
        if (dp[start][end] !== 0) {
            return dp[start][end];
        }
        for (var i = start; i < end; i++) {
            var left = foo(start, i);
            var right = foo(i + 1, end);
            var sum = left + right + matrix_sizes[start][0] * matrix_sizes[i][1] * matrix_sizes[end][1];

            if (dp[start][end] === 0) {
                dp[start][end] = sum;
            } else if (sum < dp[start][end]) {
                dp[start][end] = sum;
            }
        }
        return dp[start][end];
    }
    answer = foo(0, matrix_sizes.length - 1);
    return answer;
}

결과