자바스크립트 코딩테스트 강좌, 행렬 곱 연산 횟수의 최솟값 구하기

문제 설명

주어진 N개의 행렬에 대해, 이 행렬들을 곱할 때 필요한 연산 횟수의 최솟값을 구하는 문제입니다.
행렬 곱셈의 연산 횟수는 곱셈의 순서에 따라 크게 달라지며, 따라서 올바른 순서를 찾아야 합니다.

행렬 A의 크기가 p × q, 행렬 B의 크기가 q × r일 때,
두 행렬을 곱하는 경우의 연산 횟수는 p × q × r입니다.
여러 행렬을 한 번에 곱할 때는 효율적인 곱셈 순서를 찾아야 합니다.

예를 들어, 크기가 10 × 20, 20 × 30, 30 × 40인 세 개의 행렬을 곱할 때,
(10×20) * (20×30) * (30×40)의 경우 연산 횟수는 10 × 20 × 30 + 10 × 30 × 40 = 6000 + 12000 = 18000입니다.
(10×30) * (30×40) * (20×30)로 곱하면, 연산 횟수는 10 × 30 × 40 + 10 × 20 × 40 = 12000 + 8000 = 20000가 됩니다.
여기서 우리는 첫 번째 경우의 순서가 더 효율적임을 알 수 있습니다.

입력 형식

첫 번째 줄에는 행렬의 개수 N이 주어집니다. (1 ≤ N ≤ 100)

두 번째 줄에는 N + 1개의 정수가 공백으로 구분되어 주어집니다.
i번째 정수는 A[i] × A[i+1]의 행렬 크기를 의미합니다.
(1 ≤ A[i] ≤ 500)

출력 형식

필요한 연산 횟수의 최솟값을 하나의 정수로 출력합니다.

문제 풀이 과정

1단계: 동적 프로그래밍 기법 이해

이 문제는 행렬 곱셈 최적화문제로, 동적 프로그래밍(Dynamic Programming) 기법을 사용하여 해결할 수 있습니다.
이때, 최솟값을 구하기 위해 2차원 배열을 이용하여 각 행렬 곱셈 순서에 따른 연산 횟수를 저장할 수 있습니다.

2단계: 배열 초기화

먼저, N개의 행렬을 표현하는 m 배열을 받습니다. 이 배열의 길이는 N + 1입니다.
각 행렬의 차원 정보를 저장합니다.

let m = [10, 20, 30, 40];
        

다음으로, 연산 횟수를 저장할 2차원 배열 dp를 선언하고, Infinity로 초기화합니다.
대각선 원소는 0으로 설정합니다.

let dp = Array.from(Array(n), () => Array(n).fill(Infinity));
for (let i = 0; i < n; i++) {
    dp[i][i] = 0;
}
        

3단계: 동적 프로그래밍 테이블 완성

이중 반복문을 사용하여 행렬을 분할하고, 각각의 곱셈에 대한 최소 연산 횟수를 계산합니다.
외부 반복문은 곱셈 체인의 길이를 나타내며, 내부 반복문은 곱셈을 시도하는 인덱스를 표시합니다.

for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
        let j = i + len - 1;
        for (let k = i; k < j; k++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + m[i] * m[k + 1] * m[j + 1]);
        }
    }
}
        

4단계: 결과 출력

마지막으로, 일차원 배열 dp[0][n – 1]의 값을 출력하여 최솟값을 확인합니다.

console.log(dp[0][n - 1]);
        

전체 코드 예제

function matrixChainOrder(m) {
    const n = m.length - 1;
    let dp = Array.from(Array(n), () => Array(n).fill(Infinity));
    
    for (let i = 0; i < n; i++) {
        dp[i][i] = 0;
    }

    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            let j = i + len - 1;
            for (let k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + m[i] * m[k + 1] * m[j + 1]);
            }
        }
    }

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

let m = [10, 20, 30, 40]; // 행렬 크기
console.log(matrixChainOrder(m)); // 출력