[javascript] 프로그래머스 level 3 - 최적의 행렬 곱셈

문제 설명

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

---

문제 풀면서 어려웠던 점

• 사실상 처음에는 맨 처음과 끝을 제외한 채 그중 큰 값들을 먼저 없애는 방식(큰값을 곱하는 가운데 위치 시킴)을 생각했다
• 근데 이렇게하면 배열에 1이 있을 경우 맞지 않음(1이 있으면 1로 모든 값들을 곱해주는 게 맞다고 생각했음)
• 그러나 이렇게해도 정확성과 효율성에서 모두 통과하지 못했다.
• 그 이유는 저 방식 자체가 틀렸기 때문이다. (그러나 틀려도 이 방식이 왜 잘못된지 그때까지는 몰랐다.)
• 이 방식이 틀린 이유를 예로 들어보자면 [2, 6, 20, 15, 3]이 있다고 하자
• 가장 큰 숫자를 먼저 곱하여 없애는 방식으로 한다면 6*20*15 + 6*15*3 + 2*6*3 = 1800 + 270 + 36 = 2106
• 그러나 20*15*3 + 6*20*3 + 2*6*3 = 900 + 360 + 36 = 1296일때 값이 더 작다.
• 가장 큰 문제는 잘못된 풀이 방식을 검증하지 않고 확신했다는 것이다.
• 그리고 점화식을 어떻게 세워야 할지 고민됐다.

 

문제 풀이 방법

1. 먼저 행과 열을 숫자만 정리한 배열arr을 만든다. 

   Ex) [[3, 4], [4, 8], [8, 3]] -> arr = [3, 4, 8, 3]

2. 중간 계산값들을 저장할 배열dp를 만든다.

   행은 0~arr.length-2 인덱스, 열은 1~arr.length-1 인덱스까지만 사용하므로 이 것을 고려해서 알아서 배열 생성하면 될 것 같다.

   나같은 경우, 행은 arr.length-1크기로 만들고 열은 인덱스를 1부터 사용하므로 그냥 사용하기 편하게 arr.length크기로 생성했다.

3. getMin이라는 함수를 통해 index start부터 end까지의 행렬 곱셈의 최솟값인 dp[start][end]의 값을 구한다.

3-1. dp[start][end]에 값이 있다면 그 값을 리턴

3-2. dp[start][end]에 값이 없을 경우는 다음과 같다.

3-3. 만약 start-end가 1일 경우 dp[start][end]에 0을 저장하고 그 값을 리턴 (왜냐하면 배열 길이가 2인 경우 곱할 값이 없기 때문)

3-4. 만약 start-end가 2일 경우 dp[start][end]에 arr[start] * arr[start+1] * arr[start+2]를 저장하고 리턴 (배열 길이가 3인 경우 배열 원소 값을 모두 곱하면 된다.)

3-5. start-end가 2보다 클 경우 start end를 start+1로 나눠 계산한 값, start+2로 나눠 계산한 값, ...., end-1로 나눠 계산한 값을 모두 구해 그 중 최솟값을 선택한다.

 

이 문제에서 사용한 dp점화식은 다음과 같다.

dp[start,end] = min(dp[start,i]+dp[i,end]+arr[start]*arr[i]*arr[end]) (이때, start < i < end)

= min(dp[0,1]+dp[1,n]+arr[0]*arr[1]*arr[n], dp[0,2]+dp[2,n]+arr[0]*arr[2]*arr[n], ... , dp[0,n-1]+dp[n-1,n]+dp0]*dp[n-1]*dp[n])

---

코드

function solution(matrix_sizes) {
    let answer = 0
    
    const matrixLength = matrix_sizes.length
    const arr = Array(matrixLength+1)
    
    arr[0] = matrix_sizes[0][0]
    for(let i = 1; i < matrixLength + 1; i++) {
        arr[i] = matrix_sizes[i-1][1] 
    }
    
    const dp = Array(matrixLength).fill(0).map(_=>[...new Array(matrixLength+1).fill(-1)])
    
    const getMin = (start, end) => {
        if(dp[start][end] !== -1) {
            return dp[start][end]
        }
        if(end-start === 1) {
            dp[start][end] = 0
        } else if(end-start === 2) {
            dp[start][end] = arr[start] * arr[start+1] * arr[start+2]
        } else {
            let min = Infinity
            for(let i = 1; i < end - start; i++) {
                let value = getMin(start, start+i) + getMin(start+i, end) + arr[start] * arr[start+i] * arr[end]
                if(min > value) min = value
            }
            dp[start][end] = min
        }
        return dp[start][end]
    }

    
    return getMin(0, matrixLength);
}

---

배운 점

• 앞으로 코딩테스트 문제를 풀때 알고리즘이 바로 생각나지 않는다면, 먼저 무작위로 가능한지 살펴보고 그게 아니라면 dp방식을 생각해야 겠다.
• dp는 점화식만 잘 세우면 거의 바로 풀리기 때문에 점화식을 찾는 것에 집중해야 할 것 같다.