[백준] 파일 합치기 (11066번)/(Knuth optimization) - Python
✅문제 - 파일 합치기 (11066번)
✅필요 알고리즘 개념 - DP
🔵특정 경로를 지나는 DP
◼ 예제 입력 40 30 30 50의 경우
위의 경우에 3가지 케이스가 존재할 수 있다.
1) (1) + (2 + 3 + 4)
2) (1+2) + (3+4)
3) (1+2+3) + (4)
즉 중간 경로로 k를 선택해 지나가는 것이다.
그러므로 dp를 1차원 배열이 아닌 2차원 배열로 만들어 준다.
dp[start][end] = min(dp[start][mid] + dp[mid+1][end]) + cost[start][end]
를 만족하는 dp를 만든다.
✅필요 알고리즘 개념 - Knuth optimization
dp[start][end] = min(dp[start][mid] + dp[mid+1][end]) + cost[start][end]
이러한 점화식을 만족시키는 dp 문제에서는 특별히 Knuth's optimization을 사용할 수 있다.
이번 포스팅에서는 어떤 조건 하에서 어떻게 사용하는지만 알아보자
(우선 cost 배열은
(1) cost(b, c) ≤ cost(a, d)
(2) cost(a, c) + cost(b, d) ≤ cost(b, c) + cost(a, d) 을 만족시켜야 한다.)
이런 조건을 만족시키는 문제의 경우 dp와 함께 optimization table도 함께 만든다
opt[start][end] 에는 cost 값을 최소로 만들기 위한 mid 값을 저장한다.
( dp[start][end] = min(dp[start][mid] + dp[mid+1][end]) + cost[start][end] 을 만족시키는 mid 값을 opt[start][end]에 저장 )
opt의 초기값으로 opt[i][i] = i 을 설정한다.
여기까지가 준비단계이다.
❗❗Knuth Optimiztion의 사용법
위의 조건을 만족시키면 아래의 식을 만족시킨다.
opt[start][end-1] <= opt[start][end] <= opt[start+1][end]
이렇게 하면 기존에는 mid의 값을 start~end 까지 모두 탐색해야 하는 반면
Knuth optimization을 사용하면 탐색 범위를 줄일 수 있게 되어
시간 복잡도를 N^3 에서 N^2 까지 대폭 감소 시킬 수 있다.
✅코드 ( Knuth Optimization 사용 X )
import sys
input = sys.stdin.readline
test_num = int(input().rstrip())
for _ in range(test_num):
number = int(input().rstrip())
num_list = [0] + list(map(int,input().rstrip().split()))
psum = [0 for _ in range(number+1)]
for i in range(1,number+1):
psum[i] = psum[i-1] + num_list[i]
dp = [[0 for _ in range(number+1)] for _ in range(number+1)]
for i in range(1,number):
dp[i][i+1] = psum[i+1] - psum[i-1]
for distance in range(2,number):
for start in range(1,number+1-distance):
cost = psum[start+distance] - psum[start-1]
minimum = dp[start][start] + dp[start+1][start+distance]
for mid in range(start+1,start+distance):
minimum = min(minimum,dp[start][mid]+dp[mid+1][start+distance])
dp[start][start+distance] = cost + minimum
print(dp[1][number])
위의 방법은 Knuth optimization을 적용하지 않고
mid 값을 아래의 표와 같은 방법으로 채워서 dp[1][number]를 구하는 것이다
✅코드 ( Knuth Optimization 사용 O )
import sys
input = sys.stdin.readline
test_num = int(input().rstrip())
mx = 1e8
for _ in range(test_num):
number = int(input().rstrip())
num_list = [0] + list(map(int,input().rstrip().split()))
psum = [0 for _ in range(number+1)]
for i in range(1,number+1):
psum[i] = psum[i-1] + num_list[i]
dp = [[0 for _ in range(number+1)] for _ in range(number+1)]
opt = [[0 for _ in range(number+1)] for _ in range(number+1)]
for i in range(1,number):
dp[i][i+1] = psum[i+1]-psum[i-1]
# optimization array / 초기값 설정
for i in range(1,number+1):
opt[i][i] = i
for start in range(number-1,0,-1):
for end in range(start+1,number+1):
cost = psum[end] - psum[start-1]
minimum = mx
# Knuth Optimization 을 사용해 mid 의 범위를 축소 시킴 !!!!!
# mid의 값은 end 보다는 작아야 하므로 min()을 사용해줌
for mid in range(opt[start][end-1],min(end,opt[start+1][end]+1)):
tmp = dp[start][mid]+dp[mid+1][end]
# 최단 경로의 값과 그 때의 중간 경로 지점을 opt에 저장
if tmp <= minimum:
minimum = tmp
opt[start][end] = mid
dp[start][end] = cost + minimum
print(dp[1][number])
이 코드에서 start 와 end 의 값을 이해하기 힘들 수 있다.
우선 Knuth optimization 을 사용하는 방법은 mid의 범위를 구할 때 아래의 식을 적용하는 것이다.
opt[start][end-1] <= opt[start][end] <= opt[start+1][end]
❗❗❗ 여기서 우리의 타겟은 opt[start][end]의 범위를 구하는 것이다.
그러기 위해서는 opt[start][end-1]과 opt[start+1][end]를 알아야 한다. 아래의 표를 보자
opt[3][4]를 구하기 위해서는 opt[3][3] 과 opt[4][4]를 알아야한다.
그러므로 우리는 opt의 초기 상태에서는 opt[2][4]와 같은 값은 알 수 없다는 것이다.
그러므로 우리는 opt와 dp의 탐색 방향을 아래의 표와 같이 가기 원하는 것이다.
위의 표 방향대로 채워가면
opt[start][end-1] <= opt[start][end] <= opt[start+1][end]
위의 식을 사용함에 있어서 모든 opt 값을 채워가며 찾을 수 있기 때문에
for start in range(number-1,0,-1):
for end in range(start+1,number+1):loop에서 start와 end의 범위가 위와 같이 설정되는 것이다.
##참고
https://www.geeksforgeeks.org/knuths-optimization-in-dynamic-programming/