백준 온라인 저지(Baekjoon Online Judge) - 11049 : 행렬 곱셈 순서

https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

 

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int matrixChainMultiplication(vector<vector<int>>& matrixSizes) {
    int n = matrixSizes.size(); // 행렬의 개수
    vector<vector<int>> dp(n, vector<int>(n, 0)); // dp 배열 초기화

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;

            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + matrixSizes[i][0] * matrixSizes[k][1] * matrixSizes[j][1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

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

int main() {
    int n;
    cin >> n;

    vector<vector<int>> matrixSizes(n, vector<int>(2));

    for (int i = 0; i < n; i++) {
        cin >> matrixSizes[i][0] >> matrixSizes[i][1];
    }

    int minOperations = matrixChainMultiplication(matrixSizes);

    cout << minOperations << endl;

    return 0;
}

 

주어진 코드는 행렬 곱셈 순서를 결정하여 필요한 곱셈 연산의 최소 횟수를 구하는 문제를 해결하기 위한 코드입니다.

먼저 matrixChainMultiplication 함수는 행렬의 크기 정보를 입력으로 받아 최소 곱셈 연산의 횟수를 반환합니다. 함수 내부에서는 다음과 같은 방법으로 문제를 해결합니다.

1. n을 행렬의 개수로 초기화하고, dp라는 2차원 벡터를 생성하여 dp[i][j]에는 i번째부터 j번째까지의 행렬을 곱하는 데 필요한 최소 곱셈 연산의 횟수를 저장합니다.
2. len 변수를 2부터 n까지 반복하면서 행렬 곱셈 연산의 길이를 늘려가며 최소 곱셈 연산의 횟수를 계산합니다.
3. i를 0부터 n-len까지 반복하면서 행렬 곱셈 연산의 시작 인덱스를 결정합니다.
4. j를 i+len-1로 설정하여 행렬 곱셈 연산의 끝 인덱스를 결정합니다.
5. k를 i부터 j-1까지 반복하면서 행렬 곱셈 연산을 나누는 기준 인덱스를 결정합니다.
6. dp[i][k] + dp[k + 1][j] + matrixSizes[i][0] * matrixSizes[k][1] * matrixSizes[j][1]를 계산하여 dp[i][j]에 저장합니다. 이 값은 i부터 k까지의 행렬 곱셈 횟수, k+1부터 j까지의 행렬 곱셈 횟수, 그리고 i번째 행렬의 행 크기와 k번째 행렬의 열 크기, j번째 행렬의 열 크기를 곱한 값의 합입니다.
7. k를 변경하면서 최소값을 찾아 dp[i][j]에 저장합니다.
8. 모든 연산이 끝난 후 dp[0][n-1]의 값이 최소 곱셈 연산의 횟수가 됩니다.

'main' 함수에서는 행렬의 개수 n을 입력받고, matrixSizes라는 2차원 벡터에 행렬의 크기 정보를 입력합니다. 이후 matrixChainMultiplication 함수를 호출하여 최소 곱셈 연산의 횟수를 구하고 출력합니다.

이 코드는 동적 계획법(Dynamic Programming)의 개념을 활용하여 중복되는 계산을 피하고, 작은 부분 문제의 결과를 활용하여 큰 문제를 해결하는 방식으로 최적화되었습니다.

동적 계획법은 작은 크기의 부분 문제의 결과를 저장하고, 이를 이용하여 큰 문제의 해를 구하는 방법입니다. 이를 통해 중복되는 계산을 피하고, 효율적으로 문제를 해결할 수 있습니다.

위 코드에서는 dp라는 2차원 벡터를 활용하여 작은 부분 문제의 결과를 저장합니다. dp[i][j]는 i부터 j까지의 행렬을 곱하는데 필요한 최소 곱셈 연산의 횟수를 나타냅니다.

먼저, len 변수를 활용하여 곱셈 연산의 길이를 2부터 n까지 늘려가며 계산합니다. 그리고 i와 j를 이용하여 곱셈 연산의 시작과 끝 인덱스를 결정합니다. 이후 k를 i부터 j-1까지 반복하면서 dp[i][j] 값을 갱신합니다. 이 과정에서 k를 기준으로 작은 부분 문제의 결과인 dp[i][k]와 dp[k+1][j]를 이용하여 dp[i][j] 값을 갱신합니다.

이렇게 작은 부분 문제의 결과를 활용하여 큰 문제를 해결하면, 중복되는 계산을 피하고 최적의 해를 구할 수 있습니다.

따라서, 위 코드는 동적 계획법의 개념을 활용하여 행렬 곱셈 순서 문제를 효율적으로 해결하는 방식으로 구현되었습니다.

* 해당 게시물은 ChatGPT를 참고하여 작성되었음을 알립니다.