Knuth Optimization

다음 세 문제를 살펴보자.

 

1. Constructing String Cost

문자들의 집합 $L_{1}$, $L_{2}$, ... $L_{n}$이 있다. 각 집합의 크기를 $S_{1}$, $S_{2}$, ... $S_{n}$이라 하자. ($|L_{i}|=S_{i}$)

이제 n자리 문자열을 만들건데 $i$번째 문자는 $L_{i}$에서 선택할 것이다. 총 $S_{1}\cdot S_{2}\cdots S_{n}$ 종류의 문자열이 나올 것이다. 이제 이 모든 문자열들을 찾는데 걸리는 비용을 계산해야 한다.

 

문자열집합의 곱을 다음과 같이 정의하자. 두 문자열집합 $X$와 $Y$에 대해 $X \cdot Y = \{ a \cdot b | a \in X, b \in Y\}$. 이 때 두 문자열의 곱은 단순히 연결하는 것이다.

$L_{i}$들도 한자리 문자열들의 집합으로 볼 수 있으므로 위 문제는 $L_{1}\cdot L_{2}\cdots L_{n}$를 구하는 것으로 볼 수 있다. 일반적으로 결합법칙이 성립하므로 어떤 것을 먼저 곱하든 결과는 변하지 않을 것이다. 하지만 이제 살펴볼 비용은 어떤 것을 먼저 곱하느냐에 따라 달라진다.

 

두 집합 $X$와 $Y$를 곱하는데 걸리는 비용은 $|X|\cdot|Y|$로 정의할 수 있다. 곱셈을 진행 할수록 집합의 크기가 점점 커지므로 비용도 점점 증가할 것이다. 만약 $L_{1}\cdot L_{2}\cdots L_{n}$를 앞에서부터 차례대로 연산할 경우 다음의 비용이 소모 될 것이다.

$(S_{1} \cdot S_{2}) \cdot ((S_{1} \cdot S_{2})\cdot S_{3})\cdot((S_{1} \cdot S_{2} \cdot S_{3})\cdot S_{4}) \cdots$

 

오직 인접한 집합들끼리의 곱만 가능하다고 하면 $1 \cdot ((2\cdot 3)\cdot 4)$나 $(1 \cdot 2) \cdot (3\cdot 4)$ 등 다양한 순서가 존재한다. 이 때 우리의 목표는 연산의 순서를 잘 정의해주어 비용이 최소가 되도록 하는 것이다.

 

 

해결방법) DP를 이용

$i \leq j$에 대해 $c(i,j)$를 $L_{i}$~$L_{J}$를 곱하는데 걸리는 최소 비용으로 정의하자. $c(1,n)$을 구하면 되는데 다음과 같은 점화식을 이용해 계산할 수 있다.

$c(i,i)=0$

$c(i,j)=w(i,j)+\min_{i+1 \leq k \leq j} \{ c(i,k-1)+c(k,j)\}$ (이 때, $w(i,j)=S_{i} \cdot S_{i+1} \cdots S_{j}$)

 

모든 $(i,j)$ 쌍에 대해 $|i-j|$의 비용이 걸리므로 해당 점화식을 그냥 계산할 경우 $O(n^{3})$의 시간이 걸리게 된다.

 

 

 

2. Optimal Binary Search Trees

Binary Search Tree를 구성해야한다. 부모 노드가 왼쪽 자식 노드보다 크고 오른쪽 자식 노드보다 작은 흔한 BST이다. Root로 아무 수나 와도 상관없으므로 구성하는 방법에 따라 깊이가 $\log{n}$인 이상적인 BST, $n$인 직선형태의 BST 등 여러가지 형태가 나올 수 있다. (노드가 $n$개일 경우 카탈란 수 $C_{n}=\frac{1}{n+1} {}_{2n}C_{n}$가지 방법이 존재한다.)

 

이제 이중에서 가장 optimal한 BST를 찾아야 한다. 탐색하는데 걸리는 시간의 기댓값이 작을 수록 Optimal하다고 할 수 있다. 각 값에 접근하는데 걸리는 시간은 해당 값이 존재하는 깊이가 될 것이고 따라서 기댓값은 모든 노드들의 깊이의 평균이 될 것이다. 이 때 각 값에 접근하는 빈도가 동일하지 않을 수 있으므로 bias mean을 구해야 한다. 상황을 엄밀하게 state해보자.

 

각 노드들이 $x_{1}<x_{2}< \cdots <x_{n}$들을 값으로 갖는 BST를 구성할 것이다. 이 때 확률 $2n+1$개가 주어진다.

$p_{1}$~$p_{n}$ : 각각 $x_{i}$가 등장할 확률. 탐색에 성공하는 케이스

$q_{0}$~$q_{n}$ : $x_{i}$와 $x_{i+1}$사이의 값이 등장할 확률. 탐색에 실패하는 케이스 ($x_{0}=-\infty$, $x_{n+1}=\infty$)

 

Binary Seary Tree 예시

탐색에 실패하는 경우는 가상의 리프들을 추가하여 표현할 수 있다. 위 그림은 1~5의 값을 가지고 구성한 하나의 BST이다. 탐색에 실패할 경우 x표시된 곳에 도달하는데 값의 범위에 따라 도착하는 노드가 정해진다. 왼쪽부터 차례대로 $q_{0}$~$q_{n}$의 확률로 도달할 수 있을 것이다. 가상의 리프들을 추가하면 기댓값은 다음과 같이 계산할 수 있다.

$\sum_{i=1}^{n} p_{i} \cdot (x_{i}$ 노드의 깊이$) +\sum_{i=0}^{n} q_{i} \cdot (x_{i}$~$x_{i+1}$ 가상노드의 깊이$)$

이제 이 기댓값의 최솟값을 구하면 된다.

 

 

해결방법) 마찬가지로 DP를 이용

$i \leq j$에 대해 $c(i,j)$를 $p_{i+1}$~$p_{j}$와 $q_{i}$~$q_{j}$의 값을 가지는 노드들로 만들 수 있는 서브트리들에 대해 기댓값의 최솟값로 정의하자. $c(0,n)$을 구하면 된다.

$c(i,i)=0$

$c(i,j)=w(i,j)+\min_{i+1 \leq k \leq j} \{ c(i,k-1)+c(k,j)\}$ (이 때, $w(i,j)=(p_{i+1}+\cdots +p_{j})+(q{i}+\cdots+q_{j})$)

 

$w$의 정의만 달라지고 똑같은 점화식이 나오는 것을 확인할 수 있다. 마찬가지로 그냥 계산할 경우 $O(n^{3})$의 시간이 걸리게 된다.

 

 

3. Optimal Tournament(JAG 2015 pratice, BOJ 13092)

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

13092번: Optimal Tournament

비슷한 점화식이 나오는 것을 확인할 수 있다. 그냥 계산할 경우 $O(h\cdot n^{3})$의 시간복잡도가 나올 것이다.

 

 

 

 

위 세문제 모두 똑같은 형태의 점화식들이 등장한다. $n^{2}$개의 항을 모두 계산해주어야 하는데 각 항마다 $n$개의 최솟값을 비교 해주어야 하여 총 $O(n^{3})$의 시간복잡도를 가진다. 근데 뭔가 마음에 들지 않는다. $n$개의 최솟값인데 완전히 무작위적인 것은 아니니 뭔가 segment tree 비스무리한 걸 쓰면 $O(n^{2} \log{n})$에도 가능해야 할거 같다. 그냥은 어렵고 새로운 테크닉이 필요하다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

Knuth Optimization

다음과 같이 정의된 수열 $c(i,j) (0\leq i\leq j \leq n)$이 있다.

 

c1. $c(i,i)=0$   $for$  $0\leq i \leq n$

c2. $c(i,j)=w(i,j)+\min_{i+1 \leq k \leq j} \{c(i,k-1)+c(k,j)\}$   $for$  $0 \leq i < j \leq n$

 

단순히 있는 그대로 계산하면 $O(n^{3})$의 시간복잡도가 나오는 단순 DP이다. 여기에 아래 조건 두개가 추가되면 $O(n^2)$에 계산할 수 있게 된다.

 

w1. Quadrangle Inequalities(QI) //사각부등식

    $w(a,c)+w(b,d) \leq w(a,d)+w(b,c)$   $for$  $a \leq b \leq c \leq d$

w2. Monotone Lattice of Intervals(MLI) //단조성

    $w(i, j) \leq w(i', j')$   $for$    $[i,j] \subseteq [i',j`]$

 

 

다음 보조정리를 통해 해결하게 된다.

 

$lemma.$ $c(i,j)=w(i,j)+c(i,k-1)+c(k,j)$를 만족하는 최대의 $k$를 $K(i,j)$라 정의하면

       $K(x,y) \leq K(x,y+1) \leq K(x+1,y+1)$

 

$K$는 점화식에서 최소가 되는 그 인덱스를 의미한다. 여러개 가능하므로 편의상 최대인 것으로 정의를 하였다.

증명은 잠시 미루고 문제부터 해결 해보겠다.

 

$|y-x|$가 작은 것부터 $c(x,y)$를 계산해 나갈것이다. 이 때 $K(x,y)$도 함께 구할 것이다.

특정 $c(a,b)$를 계산하는 것을 생각해보자. 위 보조정리를 통해 모든 $a \leq k \leq b$를 확인할 필요 없이 $K(a,b-1) \leq k \leq K(a+1,b)$만 체크해주면 된다. $K(a,b-1)$과 $K(a+1,b)$는 $|y-x|$의 값이 더 작으므로 이미 계산해 놓은 값이다. 총 시간복잡도는 어떻게 나타날까?

 

$c(x+0,y+0)$는    $K(x,y-1)$~$K(x+1,y)$의 값을 확인해주면 된다.

$c(x+1,y+1)$는    $K(x+1,y)$~$K(x+2,y+1)$의 값을 확인해주면 된다.

$c(x+2,y+2)$는    $K(x+2,y+1)$~$K(x+3,y+2)$의 값을 확인해주면 된다.

$\cdots$

 

구간이 겹치지 않고 깔끔하게 분할 되는 것을 확인할 수 있다. 따라서 $|y-x|=L$인 $(x,y)$쌍들에 대해 총 $O(n)$의 시간이면 $c(x,y)$의 값들을 전부 계산해줄 수 있는 것이다. $L$은 $0$~$n$의 값을 가지므로 총 $O(n^{2})$의 시간에 $c(0,n)$까지 모든 값을 계산할 수 있다.

 

코드는 상당히 간단하다. 짜는데 얼마 안걸리기 때문에 실전에서 비슷한 형태의 점화식이 나오면 증명이 안되도 한번 짜서 제출해볼 만한 가치가 있는 풀이인 것 같다.

#include "bits/stdc++.h"
const int INF = 0x3c3c3c3c;
const int N = 1001;
int n,h;
int x[N];
int ans[51][N][N];
int k[51][N][N];

int main(void) {
    scanf("%d%d", &n, &h);
    for(int i=1; i<=n; i++) scanf("%d", x+i);
    std::sort(x, x+n+1);
    
    for(int hh=0; hh<=h; hh++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++) ans[hh][i][j]=INF;
    
    for(int i=1; i<=n; i++) ans[0][i][i]=0, k[0][i][i]=i;
    for(int hh=1; hh<=h; hh++) {
        for(int d=1; d<=n; d++) {
            for(int i=1,j=d; j<=n; i++,j++) {
                ans[hh][i][j] = ans[hh-1][i][j];
                k[hh][i][j]=k[hh-1][i][j];
                for(int kk=k[hh][i][j-1]; kk<=k[hh][i+1][j]; kk++) {
                    if(ans[hh][i][j]>ans[hh-1][i][kk]+ans[hh-1][kk+1][j]+x[j]-x[kk]) {
                        ans[hh][i][j]=ans[hh-1][i][kk]+ans[hh-1][kk+1][j]+x[j]-x[kk];
                        k[hh][i][j]=kk;
                    }
                }
            }
        }
    }
    printf("%d", ans[h][1][n]);
}

위에서 3번째로 말한 문제인 BOJ 13092번의 소스 코드이다. h들에 대해서 같은 optimization을 반복해주면 된다. 사실 점화식에 차원이 하나 더 붙기 때문에 증명이 살짝 다르다. 하지만 h<->h-1 왔다갔다 하면서 같은 부등식을 이용하면 같은 보조정리가 성립하는 것을 확인할 수 있다.

 

마지막으로 보조정리를 증명하고 마무리 하겠다. 단순 식정리로 증명된다.

 

 

$Proof$ $by$ $F.$ $F.$ $Yao$

 

$Step 1.$ $c$도 $QI$를 만족한다.

    $WTS.$ $c(x,z)+c(y,w) \leq c(x,w)+c(y,z)$    $for$ $x \leq y \leq z \leq w$ //w가 겹치는데 찰떡같이 이해해주세요.

    $Proof.$ $|w-x|$에 대한 귀납법으로 증명

    (case 0) $x=w$ 나 $x=y$, $z=w$ 등 자명한 케이스들->생략

    (case 1) $x<y=z<w$  ->  $c(y,z)=0$

            $K(x,w)=a$라 하겠다. 일반성을 잃지않고 $x \leq b$

            $c(x,z)+c(y,w) \leq w(x,z)+c(x,a-1)+c(a,y)+c(y,w)$

                                  $\leq w(x,w)+c(x,a-1)+c(a,w)$  //w에 대한 단조성 및 귀납가정

                                  $=c(x,w)$

    (case 2) $x<y<z<w$

            $K(x,w)=a$, $K(y,z)=b$라 하겠다. 일반성을 잃지않고 $a \leq b$

            $c(x,z)+c(y,w) \leq (w(x,z)+c(x,a-1)+c(a,z))+(w(y,w)+c(y,b-1)+c(b,w))$

                                  $=(w(x,z)+w(y,w))+(c(a,z)+c(b,w))+(c(x,a-1)+c(y,b-1))$

                                  $\leq (w(x,w)+w(y,z))+(c(a,w)+c(b,z))+(c(x,a-1)+c(y,b-1)$  //w와 c QI

                                  $=(w(x,w)+c(x,a-1)+c(a,w))+(w(y,z)+c(y,b-1)+c(b,z))$

                                  $=c(x,w)+c(y,z)$ // a와 b의 정의

 

 

$Step 2.$ $K(x,y) \leq K(x,y+1), K(x+1,y)$ //대칭적이므로 앞에꺼만. x=y등의 경우 생략

    $Claim.$ $x<p\leq q<y$에 대해 $c_{q}(x,y) \leq c_{p}(x,y)이면 c_{q}(x,y+1) \leq c_{p}(x,y+1)$

            ($c_{t}(i,j)=w(i,j)+c(i,t-1)+c(t,j)$)

    $Proof.$ $c(p,y)+c(q,y+1) \leq c(p,y+1)+c(q,y)$ //적당한 귀납법과 QI

            양변에 $w(x,y)+w(x,y+1)+c(x,p-1)+c(x,q-1)$을 더해주면

            $c_{p}(x,y)+c_{q}(x,y+1) \leq c_{p}(x,y+1)+c_{q}(x,y)$이고 증명됨.

    $Claim$에 의하여 위 부등식이 성립하는거 또한 자명함

 

따라서 $K(x,y-1), K(x-1,y) \leq K(x,y) \leq K(x,y+1), K(x+1,y)$

 

 

 

 

 

출처. 예전에 본거라 찾는 중 ㄱㄷ