추가 설명 — 어떤 순서로 곱했는지 되짚기

동적 계획법 ③은 표를 채워 최소 비용 28을 구했다. 표에는 숫자만 있을 뿐, 어떤 괄호 순서로 곱했는지는 어디에도 적혀 있지 않다. 이 글은 채운 표에 분할점을 함께 적어 그 순서까지 복원하는 방법을 다룬다.

이 글에서 다루는 내용

표가 담는 것은 최소 비용뿐, 어떤 괄호 순서인지의 구성은 별개다
이긴 분할점 $k$ 를 $split[i][j]$ 에 함께 기록하는 방법
$(1,n)$ 에서 재귀로 되짚어 괄호화를 복원(= 이진 파스 트리)
$d=[3,2,4,2]$ 예시로 $(M_1(M_2M_3))$ 확인, 동점과 $split$ 표 공간

값과 구성은 다르다

본편의 표 m[i][j]에는 구간 $[i,j]$ 를 곱하는 최소 곱셈 횟수만 들어 있다. m[1][3] = 28은 28이 최소라는 값만 말해줄 뿐, 어떻게 곱해야 28이 나오는지는 알려주지 않는다.

되살리려는 ‘괄호 순서’가 무엇인지부터 짚자. dp-3에서 구간 $[i,j]$ 의 답은 ‘마지막 곱을 어느 $k$ 에서 하는가’라는 결정 하나였다. 그 $k$ 가 곧 $[i,j]$ 를 감싸는 가장 바깥 괄호의 자리다. 이를테면 $[1,3]$ 이 $k=1$ 을 골랐다면 가장 바깥 괄호는 $M_1$ 과 $M_2 M_3$ 사이에서 갈라진다. 전체 순서는 $[1,n]$ 이 고른 $k$ 에서 한 번 갈라지고, 그렇게 나뉜 두 구간이 다시 각자의 $k$ 로 갈라지며 정해진다. 그러니 괄호 순서를 되살린다는 것은 각 구간이 고른 $k$ 를 알아내는 일과 같다.

문제는 그 $k$ 가 표에 남지 않는다는 점이다. 점화식은 값만 비교해 더 작은 쪽을 고르고, 어느 $k$ 가 이겼는지는 비교가 끝나는 순간 사라진다. m에는 최소 비용만 남는다. 이긴 분할점을 어떻게 붙잡아 둘지가 복원의 관건이다.

분할점을 기록하기

방법은 간단하다. m[i][j]가 갱신되는 바로 그 자리에서, 그 갱신을 낸 분할점 $k$ 를 함께 적어 두면 된다.

matrixChain의 안쪽 k 루프는 m[i][j] = min(m[i][j], ...)으로 한 줄에 갱신을 끝낸다. 이 한 줄을 조건문으로 풀면, 더 싼 분할을 찾을 때마다 m[i][j]를 갱신하는 동시에 그 분할점을 split[i][j]에 적을 자리가 생긴다. (아래 코드 조각 A.)

거꾸로 짜맞추기

분할점을 모두 적어 두면, 그 표를 따라 실제 괄호화를 거꾸로 짜맞출 수 있다. 구간 $[i,j]$ 에 대해 $build(i,j)$ 를 정의하자.

기저: $i=j$ 이면 곱할 대상이 하나뿐이므로 잎 $M_i$ 를 그대로 돌려준다.
그 외: $split[i][j]$ 에 적힌 분할점 $k$ 로 구간을 좌 $[i,k]$ ·우 $[k+1,j]$ 로 나누고, 두 결과를 괄호로 감싼다.

시작은 $build(1,n)$ 이다. 이 재귀 호출이 펼쳐지는 모양은 그 자체로 잎이 행렬, 내부 노드가 곱셈인 이진 파스 트리다.

예시로 복원

$d = [3, 2, 4, 2]$ 로 채운 표를 다시 보자. dp-3에서 구한 $split[1][3] = 1$ , $split[2][3] = 2$ 다.

$build(1,3)$ 부터 시작한다.

$split[1][3] = 1$ 이므로 좌 $[1,1]$ ·우 $[2,3]$ 으로 나뉜다: build(1,3) = "(" + build(1,1) + build(2,3) + ")".
build(1,1)은 기저다. $i=j=1$ 이므로 잎 M₁을 그대로 돌려준다.
build(2,3)은 $split[2][3]=2$ 로 좌 $[2,2]$ ·우 $[3,3]$ 으로 나뉜다. 둘 다 기저이므로 build(2,3) = "(" + M₂ + M₃ + ")" = "(M₂M₃)".
두 결과를 합치면 build(1,3) = "(M₁(M₂M₃))".

이 괄호화의 비용은 dp-3에서 오른쪽부터 묶었을 때 나온 28과 같다. 표가 말한 최소 비용 28을 실제로 만드는 괄호 순서가 바로 이것이다.

split 표를 따라 (1,3)부터 재귀로 되짚으면 파스 트리 (M₁(M₂M₃))가 나온다. 루트는 k=1, 오른쪽 내부 노드는 k=2.

코드

분할점을 기록하는 갱신과, 그 분할점을 따라가는 재귀를 코드로 옮기면 다음과 같다.

먼저 조각 A는 분할점을 기록한다. matrixChain의 안쪽 k 루프에서 min 갱신을 조건문으로 풀어, 더 싼 분할을 찾을 때마다 그 분할점을 함께 저장한다.

// split[i][j]: m[i][j]의 최소를 낸 마지막 곱의 분할점 k.
vector<vector<int>> split(n + 1, vector<int>(n + 1, 0));
// ... matrixChain 안쪽 k 루프에서 min 갱신을 조건문으로:
long long cost = m[i][k] + m[k+1][j] + 1LL*d[i-1]*d[k]*d[j];
if (cost < m[i][j]) {          // 더 싼 분할을 찾으면
    m[i][j] = cost;
    split[i][j] = k;           // 그 분할점을 기록
}

비교에 <를 쓴 자리가 중요하다. 등호 없이 엄격하게 작을 때만 갱신하므로, 같은 비용을 내는 다른 $k$ 를 만나도 분할점은 바뀌지 않는다. 동점에서 어느 쪽을 남기는지는 뒤에서 다시 짚는다.

다음으로 조각 B는 재귀로 괄호화를 복원한다. 이 재귀를 reconstruct로 옮기면 앞서 본 $build(i,j)$ 그대로다.

// split 표를 따라 [i,j]의 괄호화를 문자열로 되짚는다.
string reconstruct(const vector<vector<int>>& split, int i, int j) {
    if (i == j) return "M" + to_string(i);          // 잎: 행렬 하나
    int k = split[i][j];                            // 이 구간의 마지막 곱
    return "(" + reconstruct(split, i, k)
               + reconstruct(split, k + 1, j) + ")";
}
// 호출: reconstruct(split, 1, n)  →  "(M1(M2M3))"

미묘한 점

이 예시에는 동점이 없지만, 일반적으로 여러 분할점 $k$ 가 같은 최소 비용을 내면 유효한 괄호화가 하나가 아닐 수 있다. 조각 A의 <(등호 없음)는 그런 동점에서 먼저 찾은(가장 작은) $k$ 를 남기고 이후의 동점은 무시한다. <=로 바꾸면 나중에 찾은 $k$ 가 남아 다른 괄호화가 선택된다. 두 경우 모두 비용값 자체는 같지만, “유일한 정답”이 있어서 특정 $k$ 가 남는 게 아니다.

복원하려면 각 구간에서 이긴 분할점을 알아야 한다. split 표는 그 분할점을 $O(1)$ 에 돌려주지만, 복원의 필수 조건은 아니다. split을 저장하지 않았어도 m과 차원 배열 d만 있으면, 구간 $[i,j]$ 에서 $m[i][k]+m[k+1][j]+d_{i-1}d_k d_j$ 가 $m[i][j]$ 와 같아지는 $k$ 를 다시 찾아 되짚을 수 있다(구간마다 $O(n)$ 재탐색). $O(n^2)$ 분할점 저장은 필수 하한이 아니라 그 재탐색을 없애는 시간·공간 절충이다. 이렇게 복원된 괄호화는 잎이 $n$ 개, 내부 노드가 $n-1$ 개이며 모든 내부 노드가 자식을 두 개씩 갖는 이진 트리다.

마치며

표는 최소 비용을 계산하지만, 그 비용을 낸 분할점까지 돌려주지는 않는다. 갱신되는 자리에서 분할점 $k$ 를 함께 적어 두면(또는 나중에 m과 d에서 다시 찾으면), 비용만 담긴 표에서도 그 비용을 낸 괄호 순서를 복원할 수 있다. 비용 28을 실제로 만드는 순서가 $(M_1(M_2M_3))$ 이다.

동적 계획법 ③ →