← 문제 풀이 목록

백준 11049: 행렬 곱셈 순서

/ 14분 분량 / 문제 풀이
#알고리즘#백준#코딩테스트

C++ 언어로 Silver III 난이도의 행렬 곱셈 순서 문제를 풀이했습니다.

백준 11049: 행렬 곱셈 순서

C++ 언어로 Silver III 난이도의 행렬 곱셈 순서 문제를 풀이했습니다.

문제 소개

백준 11049번 문제는 주어진 여러 행렬을 곱할 때, 곱셈 연산 횟수를 최소화하는 최적의 괄호 배치(곱셈 순서)를 찾는 문제입니다. 각 행렬의 크기가 주어지며, 행렬의 곱셈은 결합 법칙은 성립하지만 교환 법칙은 성립하지 않습니다.

  • 문제 번호: 11049
  • 문제명: 행렬 곱셈 순서
  • 난이도: Silver III
  • 사용 언어: C++
  • 실행 시간: (제공되지 않음)
  • 메모리: (제공되지 않음)

문제 요약

n개의 행렬 A1, A2, ..., An이 주어졌을 때, A1 * A2 * ... * An 을 계산하는 데 필요한 곱셈 연산 횟수의 최솟값을 구하는 문제입니다. 행렬 i의 크기는 r_i × c_i 로 주어지며, 행렬 A_i 와 A_{i+1} 을 곱하려면 A_i의 열의 수와 A_{i+1}의 행의 수가 같아야 합니다. 이 문제를 해결하기 위해 동적 계획법(Dynamic Programming)을 사용합니다.

접근 방법

이 문제는 최적화 문제입니다. 여러 행렬을 곱할 때, 곱하는 순서에 따라 전체 곱셈 연산 횟수가 크게 달라지기 때문에, 어떤 순서로 곱하는 것이 가장 효율적인지를 찾아야 합니다. 이러한 유형의 문제는 동적 계획법으로 접근하는 것이 일반적입니다.

  1. 부분 문제 정의: dp[i][j]를 i번째 행렬부터 j번째 행렬까지 곱하는데 필요한 최소 곱셈 연산 횟수로 정의합니다.
  2. 전체 문제: 최종적으로 구하려는 값은 dp[1][n]입니다.
  3. 점화식: dp[i][j]를 계산하기 위해, i번째 행렬부터 j번째 행렬까지를 두 개의 부분 문제로 나눕니다. 예를 들어, k번째 행렬에서 분할하여 i번째부터 k번째까지의 행렬들의 곱(i ~ k)과 k+1번째부터 j번째까지의 행렬들의 곱(k+1 ~ j)을 계산한 후, 이 두 결과를 최종적으로 곱하는 경우를 생각합니다.
    • 행렬 i의 크기는 p[i] × p[i+1]입니다.
    • i번째부터 j번째까지의 행렬을 k번째에서 분할하면,
      • i ~ k 행렬들의 곱 결과는 p[i] × p[k+1] 크기를 가집니다.
      • k+1 ~ j 행렬들의 곱 결과는 p[k+1] × p[j+1] 크기를 가집니다.
      • 이 두 결과를 곱할 때 필요한 연산 횟수는 p[i] × p[k+1] × p[j+1]입니다.
    • 따라서, dp[i][j]는 모든 가능한 k ( i <= k < j )에 대해 dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1] 중 최솟값이 됩니다.
  4. 기저 사례: dp[i][i] = 0 입니다. 즉, 하나의 행렬만 곱할 때는 연산이 필요 없습니다.

이 방법을 사용하면, 작은 길이의 행렬 곱셈 문제부터 해결하고, 이를 이용하여 더 긴 길이의 행렬 곱셈 문제의 최적 해를 구할 수 있습니다.

풀이 과정

  1. 입력 처리:

    • 주어진 n개의 행렬에 대한 정보를 읽어옵니다.
    • 행렬 i의 크기를 r_i × c_i라고 할 때, 연속된 행렬 곱셈을 위해 필요한 행렬의 차원 정보를 p 벡터에 저장합니다. p[i]는 i-1번째 행렬의 열의 수이자 i번째 행렬의 행의 수와 같습니다.
    • 즉, n개의 행렬 A1, A2, ..., An이 있다면, A_i의 크기는 p[i] × p[i+1] 이 됩니다. p 벡터는 n+2 크기를 가지며 p[1]부터 p[n+1]까지 사용됩니다.

  2. DP 테이블 초기화:

    • dp 테이블을 (n+1) × (n+1) 크기로 생성하고, 모든 값을 0으로 초기화합니다. dp[i][j]는 i번째 행렬부터 j번째 행렬까지 곱하는 데 필요한 최소 비용입니다.

  3. DP 테이블 채우기:

    • 행렬 곱셈의 길이를 나타내는 len 변수를 2부터 n까지 증가시킵니다. len은 곱할 행렬의 개수를 의미합니다.
    • len이 고정되면, 시작 행렬 인덱스 i를 1부터 n - len + 1까지 반복합니다.
    • 종료 행렬 인덱스 j는 i + len - 1로 계산됩니다.
    • dp[i][j]의 초기값을 LLONG_MAX (최대값)으로 설정하여 이후 min 연산을 대비합니다.
    • 분할점 k를 i부터 j-1까지 반복합니다.
    • 각 k에 대해 dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1] 값을 계산하고, dp[i][j]의 현재 값과 비교하여 더 작은 값으로 갱신합니다.
      • dp[i][k]: i번째부터 k번째 행렬까지 곱하는 최소 비용
      • dp[k+1][j]: k+1번째부터 j번째 행렬까지 곱하는 최소 비용
      • p[i] * p[k+1] * p[j+1]: (i ~ k) 결과 행렬과 (k+1 ~ j) 결과 행렬을 곱하는 비용

  4. 결과 출력:

    • 모든 DP 테이블 채우기가 완료되면, dp[1][n]에 저장된 값이 1번째 행렬부터 n번째 행렬까지 곱하는 최소 연산 횟수입니다. 이 값을 출력합니다.

코드 설명

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 입력: 행렬 1부터 n까지 각각 r c 형태로 주어짐
    // 1-based 인덱싱 사용
    // 행렬 i의 크기: p[i] × p[i+1]
    // p[1] = 행렬 1의 행, p[2] = 행렬 1의 열 = 행렬 2의 행, ...
    // p[i] = 행렬 i의 행, p[i+1] = 행렬 i의 열
    vector<long long> p(n + 2);
    
    for (int i = 1; i <= n; i++) {
        long long r, c;
        cin >> r >> c;
        if (i == 1) p[1] = r;  // 첫 행렬의 행
        p[i + 1] = c;           // 행렬 i의 열
    }
    
    // dp[i][j] = i번째부터 j번째 행렬까지 모두 곱하는데 필요한 곱셈연산 횟수의 최솟값
    // 초기값: dp[i][i] = 0 (자기 자신은 곱할 게 없음)
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    
    // len = 대각선 인덱스. len이 고정되면 j - i가 고정 → 같은 대각선
    // len 순서로 채우면 작은 구간 먼저 보장
    // → 큰 구간 계산 시 작은 구간 값이 항상 이미 채워져 있음
    //
    // N=8 상삼각행렬 (len 표시)
    //       1    2    3    4    5    6    7    8
    //   1 [L1] [L2] [L3] [L4] [L5] [L6] [L7] [L8]
    //   2      [L1] [L2] [L3] [L4] [L5] [L6] [L7]
    //   3           [L1] [L2] [L3] [L4] [L5] [L6]
    //   4                [L1] [L2] [L3] [L4] [L5]
    //   5                     [L1] [L2] [L3] [L4]
    //   6                          [L1] [L2] [L3]
    //   7                               [L1] [L2]
    //   8                                    [L1]
    //
    // dp[1][7] (len=7) 계산 시 참조하는 칸:
    // k=1: dp[1][1](L1) + dp[2][7](L6)
    // k=2: dp[1][2](L2) + dp[3][7](L5)
    // k=3: dp[1][3](L3) + dp[4][7](L4)
    // k=4: dp[1][4](L4) + dp[5][7](L3)
    // k=5: dp[1][5](L5) + dp[6][7](L2)
    // k=6: dp[1][6](L6) + dp[7][7](L1)
    //
    // 참조하는 자리들을 줄로 연결하면 두 줄이 교차하는 규칙을 볼 수 있다.
    
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = LLONG_MAX;
            
            // i~j를 i~k와 k+1~j 두 덩어리로 쪼갬
            // i~k를 곱한 결과: p[i] × p[k+1]
            // k+1~j를 곱한 결과: p[k+1] × p[j+1]
            // 
            // 행렬 곱셈: n×m과 m×k를 곱하면 n×k이고, 곱셈연산은 n*m*k번
            // 따라서 마지막 두 행렬 p[i]×p[k+1]과 p[k+1]×p[j+1]
            // 의 곱셈 연산 횟수: p[i] * p[k+1] * p[j+1]
            //
            // e.g. (입력 순서대로 곱셈 시):
            // 행렬 1(p[1]×p[2]) × 행렬 2(p[2]×p[3]): 연산횟수 p[1]*p[2]*p[3]회
            // 결과(p[1]×p[3]) × 행렬 3(p[3]×p[4]): 누적연산횟수 p[1]*p[2]*p[3] + p[1]*p[3]*p[4]회
            // 마지막 행렬까지 끝나면 최종 누적 연산횟수: p[1]*p[2]*p[3] + p[1]*p[3]*p[4] + ... + p[1]*p[n]*p[n+1]회
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], 
                    dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]);
            }
        }
    }
    
    cout << dp[1][n] << "\n";
    
    return 0;
}

주요 부분 설명

  • vector<long long> p(n + 2);: 행렬의 차원 정보를 저장하는 벡터입니다. p[i]는 i-1번째 행렬의 열의 수이자 i번째 행렬의 행의 수가 됩니다.
  • vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));: 동적 계획법을 위한 2차원 벡터입니다. dp[i][j]는 i번째부터 j번째 행렬까지 곱하는 최소 비용을 저장합니다.
  • for (int len = 2; len <= n; len++): 곱할 행렬의 개수를 나타내는 외부 루프입니다. 길이가 2인 구간부터 시작하여 점차 길이를 늘려나갑니다.
  • for (int i = 1; i + len - 1 <= n; i++): 각 길이에 대해 가능한 모든 시작 인덱스 i를 탐색합니다.
  • int j = i + len - 1;: 현재 구간의 종료 인덱스 j를 계산합니다.
  • dp[i][j] = LLONG_MAX;: dp[i][j]를 가능한 가장 큰 값으로 초기화하여 min 함수를 통해 최솟값을 찾도록 합니다.
  • for (int k = i; k < j; k++): 구간 [i, j]를 [i, k]와 [k+1, j]로 나누는 모든 가능한 분할점 k를 탐색합니다.
  • dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]);: 분할점 k를 사용할 때의 총 비용을 계산하고, 기존 dp[i][j] 값과 비교하여 더 작은 값으로 갱신합니다. p[i] * p[k+1] * p[j+1]은 (i ~ k) 결과와 (k+1 ~ j) 결과를 곱하는 비용입니다.

복잡도 분석

  • 시간 복잡도:

    • DP 테이블을 채우는 데 세 개의 중첩된 루프가 있습니다.
    • len 루프는 n-1번 반복합니다.
    • i 루프는 n번 반복합니다.
    • k 루프는 n번 반복합니다.
    • 따라서 전체 시간 복잡도는 O(n^3) 입니다.

  • 공간 복잡도:

    • p 벡터는 n+2 크기를 가지므로 O(n) 입니다.
    • dp 테이블은 (n+1) × (n+1) 크기를 가지므로 O(n^2) 입니다.
    • 따라서 전체 공간 복잡도는 O(n^2) 입니다.

배운 점

이 문제는 행렬 곱셈 순서 문제로, 동적 계획법의 중요한 예시 중 하나입니다. 이 문제를 통해 다음을 배울 수 있었습니다.

  • 최적 부분 구조: 전체 문제의 최적 해는 부분 문제의 최적 해를 이용하여 구성될 수 있습니다.
  • 겹치는 부분 문제: 동일한 부분 문제가 여러 번 반복해서 계산될 수 있습니다.
  • DP 테이블 구성: 문제를 어떻게 작은 부분 문제로 나누고, 이 부분 문제들의 결과를 어떻게 조합하여 큰 문제의 해를 구하는지 이해했습니다. 특히, 길이 len을 기준으로 DP 테이블을 채워나가는 방식이 중요했습니다.
  • 행렬 곱셈 비용 계산: 행렬 A(r1 × c1)와 B(r2 × c2)를 곱할 때 c1 = r2이어야 하며, 결과 행렬은 r1 × c2 크기를 가지고, 곱셈 연산 횟수는 r1 × c1 × c2임을 다시 한번 인지했습니다.