[C++] 11049: 행렬 곱셈 순서

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

 

두 가지 방법으로 연습해보자.

알고리즘 분류

• 다이나믹 프로그래밍

 

 

문제설명

 

행렬은 교환법칙이 성립하지 않지만, 결합법칙은 성립한다. 그래서 예를들어, ABC의 곱을 구할 때에는

 

B x A x C 이렇게 하면 안되지만,

A x (B x C) 이렇게 하면 된다는 이야기다. 

 

이 과정에서 행렬 곱을 구할 때 가장 작은 곱셈의 연산 횟수의 최솟값을 구하자는 것이다. 아이디어는 간단하고, 실제 최적화 작업에도 도움이 될 만한 로직이다.

 

문제접근

우선 완전탐색으로 이 문제를 풀 수 있을지! 에 대해 알아보자.

for loop 을 돌면서 괄호를 잡을 것이다. 우선 ABCD의 곱을 구한다고 가정하고, 현재 index = B 라고 생각하자.

ABCD의 곱을 구하는 중, 현재 idx = B

 

그렇다면, 여기에서는 BCD에 대한 최소 괄호 관계를 찾아야 한다. 그렇다면 선택지는 3개 있다.

1. 괄호를 치지 않고 순서를 C로 넘겨준다.
2. (BC)에 괄호를 치고 D로 넘긴다.
3. (BCD)에 괄호를 치고 루프를 종료한다.

만약 1번을 선택하면, A x B x C x D 또는 A x B x ( C x  D) 인데, 일단 이건 C의 차례이니 패스하고 2,3번에 집중하자.

 

만약 2번을 선택한다면, A x (B x C) x D 를 구하면 된다. 이 경우에는 즉, 다음 그림과 같은 연산을 구하면 된다.

즉, (BC의 곱에 필요한 연산) +  A x B' x D (B' = BC) 를 구하면 된다. 이를 코드로 나타내면,

go(ABCD) = go(AB'D) + go(BC)

 

실제로 예를 들어 보자. 문제의 예와 비슷하게,

A = 5 x 3
B = 3 x 2
C = 2 x 6
D = 6 x 4

 

라고 생각하면, go(BC) = 3 x 2 x 6 = 36 이고, B' = 3 x 6 이므로, 총합을 구하면

go(ABCD) = go(AB'D) + go(BC)
	 = go(AB') + go(A'D) + go(BC) // A' = AxB'
         = 5 x 3 x 6 + 5 x 6 x 4 + 3 x 2 x 6
         = 90 + 120 + 36
         = 246

 

위와 같다. 만약 3가지 이상 행렬을 곱한다면, 앞에서부터 2개씩 곱해주면서 더해주면 된다.

 

마찬가지로, 만약 3번을 선택한다면, A x B' (B' = BCD)를 구하면 된다. 즉,

go(ABCD) = go(AB') + go(BCD)

 

이렇게 문제를 푸는 대략적인 방법을 익혔다. 그럼 이제 이걸 완전탐색으로 구할 수 있나? 입출력조건을 보면,

 

N = 500으로 작긴 하지만, 첫 번째 index에서 괄호를 닫기 위해 500번, 두 번째 index 가 만약 1이라면 499번, .... 이렇게 가므로,  500!이 걸리므로, 완전탐색으로는 해결할 수 없다.

 

Plan A : 완전탐색이 실패했으므로,  우리는 Plan B로 가야 한다.

 

Plan B : 다이나믹 프로그래밍으로 풀 수 있나?

 

다이나믹 프로그래밍으로 풀기 위해서는 다음 조건을 만족해야 한다.

1. Optimal Substructure : 문제의 최적해가 부분 문제의 최적해로 구성되어 있는가?
2. Overlapping Subproblems : 부분 문제들이 겹쳐서, 메모이제이션 테크닉을 이용할 수 있는가?

우선 1번 문제부터 생각해보자. 앞서 그림을 다시 한번 보자.

 

여기서 B'의 row 정보와 column 정보, B와 C의 row 정보와 column 정보를 비교해보자.

B = 3 x 2
C = 2 x 6
B' = 3 x 6

 

이 경우에 ABCD 순서대로와 AB'CD를 구한다고 생각해보면, 인터페이스는 A와 B'의 연결, B'와 D의 연결을 비교해야 한다.

A와 B'의 연결의 경우, A 가 5 x 3 이므로, 5 x 3 x 3(B'의 row)를 곱하는 건 필수적이고, A'D에서는  5(A의 row) x 6(C의 col) x 4(D의 row)를 곱하는 것 역시 필수적이다. 

BC에 괄호를 안치는 경우도 생각해보자. A x B의 과정에서 필수적인 연산(5x3x3)이 활용되고, 이후 (ABC) x D 를 하는 과정을 생각해보면 역시 필수적인 연산(5x6x4)가 활용된다.

 

따라서, 어떤 부분 문제로 분할하던 간에, 부분 문제를 합치는 과정은 변하지 않는다. 따라서 Optimal Substructure가 성립한다.

 

두 번째 경우인 Overlapping subproblems는 당연히 성립함을 알 수 있다. ABCD에서 A부터 시작한다고 생각하면, go(BCD), go(CD), go(D)를 차례로 호출할 것이고, go(BCD) 과정에서 go(CD)와 go(D)를 호출할 것이므로 겹치는 부분이 존재한다.

 

이제 DP로 풀 수 있음을 확인했으니 두 가지 경우만 정의하면 된다.

 

1. DP 배열의 정의 : int dp[504][504] ( i부터 j까지의 최소 행렬 곱셈 연산 수)
2. base case : dp[i][j] 에서 (i == j) 인 경우, 1개 행렬에서는 곱이 없으므로 0이다.

 

정답코드(Top-Down)

이를 통해 코드를 구현하면 다음과 같다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}

vector<pll> v;
ll dp[504][504];
ll n, r, c;

ll go(int _s, int _e)
{
  if (_s == _e) return 0;
  
  ll& ret = dp[_s][_e];
  if (~ret) return ret;

  ret = 1e12;
  for (int i = _s; i < _e; i++)
  {
    ret = min(ret, go(_s, i) + go(i + 1, _e) + v[_s].first * v[i].second * v[_e].second);
  }

  return ret;
}

int main()
{
  fastIO();
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> r >> c;
    v.push_back({r,c});
  }
  memset(dp, -1, sizeof(dp));

  cout << go(0, n-1) << endl;
}

 

문제를 푼 결과 172ms가 나온다. 이는 다른 풀이들에 비해 시간이 좀 긴거 같다.

 

상향식(bottom-up) 방법으로 최적화

그렇다면 시간을 좀 줄여보기 위해, 상향식 (bottom-up) 방법을 도입하자.

상향식 방법은 하향식 방법에 비해 조금 어려운데, 이는 직관적이지 않은 방법이기 때문이다. 큰것을 작은 문제로 분할한다는 것이 DP의 철학인데, 그 반대 과정을 생각해야한다.

 

우선 base case부터 시작하자. base case는 행렬 한 개밖에 없는 경우는, 곱셈을 하지 않으므로 dp[i][i] = 0이다.

이제 length를 늘려가면서 생각해보자. 만약 행렬 2개의 경우, 방법은 정해져있다.

dp[i][i+1] = matrix[i].row * matrix[i].col * matrix[i+1].col

 

그러면 length를 하나 더 늘려서 행렬 3개인 경우는? 2가지이다.

• 왼쪽부터 구하기 : dp[i][i+2] = min( dp[i][i+2], dp[i][i+1] + matrix[i].row * matrix[i+1].col * matrix[i+2].col )
• 뒤에 두개부터 구하기 : dp[i][i+2] = min (dp[i][i+2], dp[i+1][i+2] + matrix[i].row * matrix[i].col * matrix[i+2].col)

이런 식으로 length를 늘려주면서 구해주면 된다.

 

정답코드(bottom-up)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
}

pii mat[504];
int dp[504][504];

int main()
{
  int n;
  cin >> n;
  
  for (int i = 0; i < n; i++)
  {
    cin >> mat[i].first >> mat[i].second;
  }
  
  for (int len = 1; len < n; len++)
  {
    for (int i = 0; i < n - len; i++)
    {
      dp[i][i+len] = INT_MAX;
      for (int j = i; j < i + len; j++)
      {
        dp[i][i+len] = min(dp[i][i+len], 
                          dp[i][j] + dp[j+1][i+len] 
                          + mat[i].first * mat[j].second * mat[i+len].second);
      }
    }
  }

  cout << dp[0][n-1] << endl;
}

 

푼 결과 이번에는 28ms로 잘 나오는 모습을 볼 수 있다.