크누스 최적화

이 글은 시리즈의 일부입니다. 먼저 이전 글을 모두 읽기를 권장합니다.

이전 최적화 방법은 $opt[i, j] \leq opt[i, j + 1]$이라는 사실에 기반합니다.

$opt$가 두 번째 인자에 대해서도 단조롭다는 점에 주목하면 점근적 복잡도를 더 개선할 수 있습니다.

구간 덮기 문제에서도 대략 같은 이유로 이것이 성립합니다. 사용할 수 있는 구간이 더 많아지면, 최적해에서 마지막 구간은 이전보다 결코 길어지지 않습니다.

#알고리즘

얻은 부등식을 가장 직접적인 방식으로 활용합시다. 각 상태마다 $opt[i - 1, j]$부터 $opt[i, j + 1]$까지의 모든 원소를 단순히 전부 살펴보겠습니다.

상태 $(i, j)$에 도달했을 때 경계 $opt[i - 1, j]$와 $opt[i, j + 1]$이 이미 계산되어 있도록, $i$는 증가하는 순서로, $j$는 감소하는 순서로 순회하겠습니다.

for (int i = 1; i <= n; i++) {
    for (int j = m; j >= 1; j--) {
        for (int k = opt[i - 1][j]; k <= opt[i][j + 1]; k++) {
            int val = f[i + 1][k-1] + cost(i, j);
            if (val < f[t][k])
                f[t][k] = val, opt[i][j] = i;
        }
    }
}

구현은 매우 간결합니다. 기본 풀이보다 겨우 3줄 더 길 뿐입니다.

#점근적 복잡도

이 방법은 빠르게 동작한다는 것이 밝혀집니다. 그 이유를 이해하기 위해, 각 상태마다 살펴보게 될 원소의 개수를 써 보고 이를 모두 더해 봅시다: