Knuth's Optimization

크누스 최적화(Knuth's Optimization)는 동적 프로그래밍(DP)에서 특정 유형의 문제를 더 효율적으로 해결하기 위해 사용. 주로 분할 정복 및 DP를 사용하는 문제에서 특히, 점화식이 특정 성질을 만족하는 경우에 최적화가 가능.

일반적인 $O(n^3)$의 시간 복잡도를 $O(n^2)$로 줄일 수 있다.

조건

크누스 최적화를 적용하려면 두 가지 주요 조건이 충족되어야 합니다:

1. 점화식의 적합성: DP 점화식이 특정 형태를 가져야 합니다.
2. 사각 부등식(사각 부등식의 단조 증가 조건): 최적의 분할점이 단조 증가해야 합니다.

점화식의 적합성

DP 점화식이 다음과 같은 형태를 가져야 합니다:
$DP[i][j] = \min_{k \leq m < j} { DP[i][m] + DP[m+1][j] } + C[i][j]$
여기서 $C[i][j]$는 구간 $[i, j]$의 비용입니다.

이 점화식의 형태를 가지는 문제는, 구간을 분할하여 각 부분의 비용을 합하는 방식으로 해결할 수 있는 문제들입니다.

사각 부등식

사각 부등식은 다음을 만족해야 합니다:
$\text{opt}[i][j-1] \leq \text{opt}[i][j] \leq \text{opt}[i+1][j]$
여기서 $\text{opt}[i][j]$는 구간 $[i, j]$에 대한 최적의 분할점.

이 조건은 간단히 말해, 구간의 끝점을 오른쪽으로 이동시킬 때 최적의 분할점도 오른쪽으로 이동해야 한다는 의미입니다. 즉, 최적의 분할점이 단조 증가해야 합니다.

예제 문제

이제, 위의 조건을 만족하는 구체적인 예제 문제를 살펴보겠습니다. 대표적인 예는 행렬 체인 곱셈(Matrix Chain Multiplication) 문제입니다.

행렬 체인 곱셈 문제

행렬 체인 곱셈 문제는 주어진 행렬들을 특정 순서로 곱하는데 필요한 최소 연산 횟수를 찾는 문제입니다.

https://mathbang.net/562#gsc.tab=0

행렬의 곱셈, 행렬의 거듭제곱

https://namu.wiki/w/%ED%96%89%EB%A0%AC%EA%B3%B1

행렬곱

 

문제 설명

여러 개의 행렬 $A_1, A_2, …, A_n$이 주어졌을 때, 이 행렬들을 곱하는 최적의 순서를 찾는 것입니다. 행렬 $A_i$의 크기는 $p_{i-1} \times p_i$입니다.

DP 점화식

행렬 체인 곱셈 문제의 점화식은 다음과 같습니다:
$
DP[i][j] = \min_{i \leq k < j} { DP[i][k] + DP[k+1][j] + p_{i-1} \times p_k \times p_j }
$
이 점화식은 크누스 최적화의 첫 번째 조건을 만족합니다.

사각 부등식

행렬 체인 곱셈 문제의 경우 최적 분할점이 단조 증가하는 성질을 가집니다. 즉, $\text{opt}[i][j-1] \leq \text{opt}[i][j] \leq \text{opt}[i+1][j]$가 성립합니다.

행렬의 크기가 아래와 같다고 가정해 보겠습니다:

• $A_1$: 10 x 30
• $A_2$: 30 x 5
• $A_3$: 5 x 60
• $A_4$: 60 x 10

동적 계획법을 사용하여 최적 분할점을 구하고 이를 표로 정리하면 다음과 같습니다. 여기서 $m[i, j]$는 행렬 $A_i$부터 $A_j$까지의 최적 곱셈 비용을 나타내고, $s[i, j]$는 최적 분할점을 나타냅니다.

i	j	최적 분할점 $s[i, j]$
1	2	1
1	3	2
1	4	3
2	3	2
2	4	3
3	4	3

이 표에서 $s[i, j]$가 단조 증가하는 것을 확인할 수 있습니다. 즉, $s[i, j]$는 $i < j$에 대해 항상 증가합니다.

예제 코드

아래는 행렬 체인 곱셈 문제에 크누스 최적화를 적용한 예제 코드입니다:

def matrix_chain_order(p):
    n = len(p) - 1
    DP = [[0] * n for _ in range(n)]
    opt = [[0] * n for _ in range(n)]

    for i in range(n):
        opt[i][i] = i

    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            DP[i][j] = float('inf')
            for k in range(opt[i][j-1], opt[i+1][j] + 1):
                q = DP[i][k] + DP[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                if q < DP[i][j]:
                    DP[i][j] = q
                    opt[i][j] = k

    return DP[0][n-1]

# 행렬의 크기를 나타내는 리스트
p = [40, 20, 30, 10, 30]
print(matrix_chain_order(p))  # 최소 곱셈 연산 횟수를 출력

이 예제에서 우리는 행렬 체인 곱셈 문제에 크누스 최적화를 적용하여 DP 테이블을 효율적으로 채웁니다.

동작 방식

크누스 최적화는 다음과 같은 단계로 동작합니다:

1. 초기화: DP 테이블과 최적 분할점 테이블을 초기화합니다.
2. 점화식 계산: 점화식을 통해 DP 값을 계산합니다. 이 때 최적 분할점을 이용해 계산 범위를 줄입니다.
3. 최적 분할점 갱신: 각 구간에 대해 최적 분할점을 계산하고 갱신합니다.

예제 코드 (Python)

아래는 크누스 최적화를 적용한 예제 코드입니다. 이 예제에서는 단순히 비용이 $C[i][j]$인 경우를 가정합니다.

def knuth_optimization(n, C):
    # DP 테이블 초기화
    DP = [[float('inf')] * (n + 1) for _ in range(n + 1)]
    opt = [[0] * (n + 1) for _ in range(n + 1)]
    
    # 기본 비용 초기화 (예: C[i][i] = 0 인 경우)
    for i in range(n + 1):
        DP[i][i] = 0
        opt[i][i] = i
    
    # 점화식 적용
    for l in range(2, n + 1):  # l은 부분 문제의 길이
        for i in range(1, n - l + 2):
            j = i + l - 1
            DP[i][j] = float('inf')
            
            # 최적 분할점의 범위 제한
            for k in range(opt[i][j-1], opt[i+1][j] + 1):
                cost = DP[i][k] + DP[k + 1][j] + C[i][j]
                if cost < DP[i][j]:
                    DP[i][j] = cost
                    opt[i][j] = k

    return DP[1][n]

# 예제 비용 행렬
C = [[0, 0, 0, 0], [0, 0, 2, 5], [0, 0, 0, 3], [0, 0, 0, 0]]
n = 3

print(knuth_optimization(n, C))

이 예제에서는 문제를 해결하기 위해 최적의 분할점을 찾는 과정을 효율적으로 수행합니다. 크누스 최적화는 이처럼 특정 유형의 문제에서 계산 범위를 줄여 성능을 크게 향상시킬 수 있습니다.

--- ---

기본 동적 프로그래밍 코드 (크누스 최적화 적용 전)

구간 길이 $l$	시작점 $ i $	끝점 $ j $	내부 루프 (분할점)	연산 횟수
2	1	2	1	1
2	2	3	2	1
2	3	4	3	1
3	1	3	1, 2	2
3	2	4	2, 3	2
4	1	4	1, 2, 3	3
…	…	…	…	…
$ n $	1	$ n $	1, 2, …, $n-1$	$n-1$

• 구간 길이가 클수록 내부 루프에서 모든 가능한 분할점을 다 탐색하므로 연산 횟수가 기하급수적으로 증가합니다.

크누스 최적화를 적용한 동적 프로그래밍 코드

구간 길이 $l $	시작점 $i $	끝점 $j $	탐색 범위 (분할점 $k $)	연산 횟수
2	1	2	opt[1][1] to opt[2][2]	1
2	2	3	opt[2][2] to opt[3][3]	1
2	3	4	opt[3][3] to opt[4][4]	1
3	1	3	opt[1][2] to opt[2][3]	2
3	2	4	opt[2][3] to opt[3][4]	2
4	1	4	opt[1][3] to opt[2][4]	2
…	…	…	…	…
( n )	1	( n )	opt[1][n-1] to opt[2][n]	2

• 구간 길이가 커져도 최적 분할점의 범위를 제한하여 탐색하므로, 연산 횟수가 크게 증가하지 않습니다.

시간 복잡도의 차이

• 기본 동적 프로그래밍 코드: 각 구간에 대해 모든 분할점을 다 탐색하므로, 시간 복잡도가 $O(n^3) $입니다.
• 크누스 최적화를 적용한 코드: 최적 분할점이 단조 증가하는 성질을 이용해 탐색 범위를 줄이므로, 시간 복잡도가 $O(n^2) $입니다.

예제 비교: $n = 6 $인 경우

기본 DP 코드

def matrix_chain_order(p):
    n = len(p) - 1
    DP = [[0] * n for _ in range(n)]
    
    for l in range(2, n + 1):
        for i in range(n - l + 1):
            j = i + l - 1
            DP[i][j] = float('inf')
            for k in range(i, j):
                q = DP[i][k] + DP[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
                if q < DP[i][j]:
                    DP[i][j] = q

    return DP[0][n-1]

# 행렬의 크기를 나타내는 리스트
p = [30, 35, 15, 5, 10, 20, 25]
print(matrix_chain_order(p))  # 최소 곱셈 연산 횟수를 출력

크누스 최적화를 적용한 코드

def knuth_optimization(n, C):
    DP = [[float('inf')] * (n + 1) for _ in range(n + 1)]
    opt = [[0] * (n + 1) for _ in range(n + 1)]
    
    for i in range(n + 1):
        DP[i][i] = 0
        opt[i][i] = i
    
    for l in range(2, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1
            DP[i][j] = float('inf')
            
            for k in range(opt[i][j-1], opt[i+1][j] + 1):
                cost = DP[i][k] + DP[k + 1][j] + C[i][j]
                if cost < DP[i][j]:
                    DP[i][j] = cost
                    opt[i][j] = k

    return DP[1][n]

# 예제 비용 행렬
C = [[0, 0, 0, 0, 0, 0, 0],
     [0, 0, 15750, 7875, 9375, 11875, 15125],
     [0, 0, 0, 2625, 4375, 7125, 10500],
     [0, 0, 0, 0, 750, 2500, 5375],
     [0, 0, 0, 0, 0, 1000, 3500],
     [0, 0, 0, 0, 0, 0, 5000],
     [0, 0, 0, 0, 0, 0, 0]]
n = 6

print(knuth_optimization(n, C))

결과

• 기본 DP 코드는 모든 분할점을 탐색하므로 $O(n^3)$의 복잡도를 가지며, $n = 6$일 경우 최대 약 $216$번의 연산이 필요합니다.
• 크누스 최적화를 적용한 코드는 최적 분할점 범위를 탐색하므로 $O(n^2)$의 복잡도를 가지며, $n = 6$일 경우 최대 약 $72$번의 연산이 필요합니다.

요약

크누스 최적화를 적용하지 않은 기본 동적 프로그래밍 코드에서는 각 구간에 대해 모든 가능한 분할점을 다 탐색하므로 연산 횟수가 많아지고, 시간 복잡도가 $O(n^3)$ 로 높습니다. 반면, 크누스 최적화를 적용한 코드는 최적 분할점의 범위를 제한하여 탐색하므로 연산 횟수가 줄어들고, 시간 복잡도가 $O(n^2)$ 로 감소합니다.

 

https://suri78.tistory.com/16

[알고리즘]Knuth's optimization 크누스 최적화

https://makeameme.org/meme/that-costs-how

https://80000coding.oopy.io/4debdb98-5033-47c0-9f8b-4f9a7d2cfc2b

연쇄행렬 최소곱셈 알고리즘(Matrix chain multiplication)

 

https://hseungyeon.tistory.com/313

[다이나믹 프로그래밍] ★★ 11066번 - 파일 합치기

https://www.youtube.com/watch?v=4OdIDIYLHlY

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