동적 계획법 ③ — 구간을 어디서 자를 것인가

동적 계획법 ②는 마지막 원소를 포함하는가 라는 결정 하나로 점화식을 세웠다. 이번엔 결정의 대상이 원소가 아니라 구간이다. 이 구간의 마지막 곱셈을 어디서 하는가.

이 포스트에서 다루는 내용

곱셈 순서가 비용을 바꾼다: 같은 결과, 다른 곱셈 횟수
구간을 자르는 결정에서 점화식 $M[i,j]=\min_k(\cdots)$ 유도
짧은 구간부터 채우는 2차원 표로 $O(n^3)$ 에 풀기
(더 나가면) 어떤 괄호 순서인지 복원

곱셈 순서가 비용을 바꾼다

행렬 $(p\times q)$ 와 $(q\times r)$ 을 곱하면 결과는 $p\times r$ 행렬이고, 스칼라 곱셈은 $p\cdot q\cdot r$ 번 필요하다. 행렬 곱은 결합법칙이 성립해 어떤 순서로 괄호를 묶어도 결과는 같다. 곱셈 횟수는 괄호 위치에 따라 달라진다.

세 행렬 $M_1$ ( $3\times2$ ), $M_2$ ( $2\times4$ ), $M_3$ ( $4\times2$ )를 곱한다고 하자. 괄호를 어디에 두느냐로 두 가지를 비교해 본다.

왼쪽부터 묶기 $((M_1M_2)M_3)$ : $M_1M_2$ 는 $3\cdot2\cdot4=24$ 번, 그 결과( $3\times4$ )에 $M_3$ 을 곱하면 $3\cdot4\cdot2=24$ 번이다. 합쳐 $24+24=48$ 번.

오른쪽부터 묶기 $(M_1(M_2M_3))$ : $M_2M_3$ 는 $2\cdot4\cdot2=16$ 번, $M_1$ 과 그 결과( $2\times2$ )를 곱하면 $3\cdot2\cdot2=12$ 번이다. 합쳐 $16+12=28$ 번.

같은 세 행렬, 같은 결과인데 곱셈 횟수는 48번과 28번으로 갈린다. 괄호를 어디에 두느냐가 비용을 결정한다.

마지막 곱셈을 어디서 하는가

$M_i \times \cdots \times M_j$ 를 곱하는 데 드는 최소 곱셈 횟수를 $M[i,j]$ 로 정의한다. 구하려는 답은 $M[1,n]$ 이다.

괄호화 하나를 고정해 놓고 가장 바깥 괄호를 본다. 사슬 전체를 감싸는 최상위 괄호는 사슬을 둘로 가르는 마지막 곱 하나로 요약된다. 그 분할점을 $k$ ( $i \le k < j$ )라 하면, 왼쪽은 $M_i \cdots M_k$ , 오른쪽은 $M_{k+1} \cdots M_j$ 이고 두 결과를 마지막에 한 번 곱한다.

바깥에서 어떤 행렬이 앞뒤로 더 곱해지든 $M[i,k]$ 와 $M[k+1,j]$ 의 값 자체는 바뀌지 않는다(부분 구간 독립성). 마지막 곱의 비용은 왼쪽 결과가 $d_{i-1}\times d_k$ 행렬, 오른쪽 결과가 $d_k\times d_j$ 행렬이므로 $d_{i-1}\,d_k\,d_j$ 번이다. 어느 $k$ 가 최선인지 미리 알 수 없으니 가능한 모든 $k$ 를 시도해 가장 작은 값을 취한다.

M[i,j] = \min_{i \le k < j}\big(M[i,k] + M[k+1,j] + d_{i-1}\,d_k\,d_j\big)

기저 조건

행렬이 하나뿐이면 곱할 대상이 없어 곱셈이 필요 없다.

M[i,i] = 0

정리 1최적 부분구조

$M[i,k]$ 와 $M[k+1,j]$ 가 각각 구간 $[i,k]$ , $[k+1,j]$ 에서의 최소 곱셈 횟수이면

M[i,j] = \min_{i \le k < j}\big(M[i,k] + M[k+1,j] + d_{i-1}\,d_k\,d_j\big)

이다.

증명. $M[i,j]$ 를 만드는 최적 괄호화 하나를 고정한다. 이 괄호화의 최상위(마지막) 곱은 어떤 분할점 $k^*$ ( $i \le k^* < j$ )에서 사슬을 왼쪽 $M_i\cdots M_{k^*}$ 과 오른쪽 $M_{k^*+1}\cdots M_j$ 로 가른다.

왼쪽 부분의 곱셈 횟수가 $M[i,k^*]$ 보다 크다면, 왼쪽만 $M[i,k^*]$ 를 내는 괄호화로 바꿔치기해도 오른쪽 부분과 마지막에 합치는 비용은 그대로이므로 전체 곱셈 횟수가 줄어든다. 이는 고정한 괄호화가 최적이라는 가정과 어긋난다. 그러므로 왼쪽 부분의 값은 정확히 $M[i,k^*]$ 다. 오른쪽 부분도 같은 논법으로 정확히 $M[k^*+1,j]$ 다. 두 값에 마지막 곱 비용을 더하면

M[i,j] = M[i,k^*] + M[k^*+1,j] + d_{i-1}\,d_{k^*}\,d_j

이다. $k^*$ 는 $i \le k < j$ 범위에서 후보가 될 수 있는 값 중 하나일 뿐이므로, 우변은 그 범위 전체의 최솟값보다 작을 수 없다. 즉 $M[i,j] \ge \min_{i \le k < j}\big(M[i,k]+M[k+1,j]+d_{i-1}d_kd_j\big)$ 이다(하계).

거꾸로, 각 $k$ 에 대해 왼쪽을 $M[i,k]$ 를 내는 괄호화로, 오른쪽을 $M[k+1,j]$ 를 내는 괄호화로 잡고 마지막에 한 번 곱하면, 이는 구간 $[i,j]$ 에서 실제로 만들 수 있는 하나의 괄호화다. $M[i,j]$ 는 그런 모든 괄호화 중 최소 비용이므로 $M[i,j] \le M[i,k]+M[k+1,j]+d_{i-1}d_kd_j$ 가 모든 $k$ 에서 성립하고, 따라서 $M[i,j] \le \min_{i \le k < j}\big(\cdots\big)$ 이다(상계). 두 방향을 합치면 $M[i,j] = \min_{i \le k < j}\big(M[i,k]+M[k+1,j]+d_{i-1}d_kd_j\big)$ 이다. ∎

구간 [i,j]를 k에서 자르면 왼쪽 M[i,k], 오른쪽 M[k+1,j], 합치는 비용 d_{i-1}·d_k·d_j. 모든 k 중 최소가 답이다.

작은 구간부터 채우기

$M[i,j]$ 는 자기보다 짧은 구간 $M[i,k]$ , $M[k+1,j]$ 만 참조한다( $i \le k < j$ 이므로 두 구간 모두 $[i,j]$ 보다 진짜 짧다). 구간 길이 1(기저)부터 시작해 길이를 늘려 가며 채우면, $M[i,j]$ 를 계산할 차례에 필요한 참조가 항상 먼저 준비돼 있다.

// d[0..n]: Mᵢ 는 d[i-1] x d[i] 행렬.  M₁ x … x Mₙ 의 최소 곱셈 횟수.
long long matrixChain(const vector<int>& d, int n) {
    vector<vector<long long>> m(n + 1, vector<long long>(n + 1, 0));  // m[i][i]=0: 한 행렬은 곱 불필요
    for (int len = 2; len <= n; len++)              // 구간 길이 2..n
        for (int i = 1; i + len - 1 <= n; i++) {    // 구간 [i, j]
            int j = i + len - 1;
            m[i][j] = LLONG_MAX;
            for (int k = i; k < j; k++)             // 마지막 곱을 (i..k)(k+1..j)로
                m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + 1LL*d[i-1]*d[k]*d[j]);
        }
    return m[1][n];
}

곱 $d_{i-1}d_k d_j$ 가 구간마다 쌓이면 값이 32비트 정수를 넘기 쉬워, 표와 반환형을 64비트(long long)로 둔다.

$d=[3,2,4,2]$ 로 표를 채워 본다. 길이 2 — $M[1,2]=3\cdot2\cdot4=24$ , $M[2,3]=2\cdot4\cdot2=16$ . 길이 3 — $M[1,3]=\min(M[1,1]+M[2,3]+3\cdot2\cdot2,\; M[1,2]+M[3,3]+3\cdot4\cdot2)=\min(0+16+12,\;24+0+24)=\min(28,48)=28$ . 정답 $M[1,3]=28$ 이다.

삼각 표를 대각선(구간 길이) 순으로 채운다. d=[3,2,4,2]에서 M[1,2]=24, M[2,3]=16, M[1,3]=28.

비용 따지기

채울 칸은 구간 $[i,j]$ ( $i\le j$ )마다 하나씩이라 $O(n^2)$ 개다. 칸 하나를 채우는 데는 분할점 $k$ 후보를 최대 $n$ 개까지 시도하므로 $O(n)$ 이 걸린다. 칸의 개수에 칸당 시간을 곱하면 전체 시간은 $O(n^2)\cdot O(n)=O(n^3)$ 이고, 표 자체를 저장하는 공간은 $O(n^2)$ 이다.

칸의 개수 $O(n^2)$ 는 채워야 할 부분 문제의 개수일 뿐, 전체 계산 시간이 아니다. 칸마다 최대 $O(n)$ 의 안쪽 반복(모든 $k$ 시도)이 더 붙어야 전체 $O(n^3)$ 이 나온다.

더 나가면

지금까지의 코드는 최소 비용 $M[1,n]$ 만 돌려준다. 실제로 어떤 괄호 순서였는지, 즉 각 구간에서 어느 $k$ 로 나눴는지는 이 값만으로 알 수 없다. 칸마다 최선의 분할점 $k$ 를 함께 저장해 두면 $M[1,n]$ 에서 시작해 저장된 $k$ 를 따라 거꾸로 내려가며 실제 괄호화를 되짚을 수 있다. 그 복원 방법은 추가 설명 — 어떤 순서로 곱했는지 되짚기에서 따로 다룬다.

마치며

dp-1은 이미 주어진 점화식을 계산했다. dp-2는 “마지막 원소를 포함하는가”라는 결정 하나로 점화식 자체를 세웠다. 이번 dp-3은 그 결정의 대상을 원소에서 구간으로 확장해, “이 구간의 마지막 곱셈을 어디서 하는가”라는 질문에서 $M[i,j]=\min_{i\le k<j}(M[i,k]+M[k+1,j]+d_{i-1}d_kd_j)$ 를 얻었다. 짧은 구간의 답이 항상 먼저 준비되도록 길이 순으로 표를 채우면 $O(n^3)$ 시간에 답이 나온다.

동적 계획법 ② →