다이내믹 프로그래밍

Dynamic Programming

Dynamic Programming: 문제를 하위 문제로 나뉘어 푼 다음 그 결과를 바탕으로 문제 해결
(예) 피보나치 수열 솔루션 Fib(n) = Fib(n-1) + Fib(n-2)

def fib(n):
	if n == 0 or n == 1:
    	return 1
    return fib(n-1) + fib(n-2)
print(fib(5))

• 같은 값을 여러번 계산
• fib(0)과 fib(1)의 호출 횟수를 합하면 fib(n)
• 시간, 공간 복잡도: O(2^N)

이 문제를 DP로 해결하려면?

n = 5
fib = [0 for i in range(n+1)]
fib[0] = 1
fib[1] = 1
for i in range (2, n+1):
	fib[i] = fib[i-1] + fib[i-2]
print(fib[5])

Top-down DP

1. DP 배열 생성 (방문 check 위해 -1로 초기화)
2. 초기값 설정, 반환
3. 이미 계산된 값 반환
4. 점화식 계산, 저장, 반환

n = 5
dp = [-1 for i in range(n+1)]

def fib(x): 
	if x == 0 or x == 1:
    	dp[x] = 1 # 초기값 설정, 반환
        return dp[x]
    if dp[x] != -1:
    	return dp[x] # 이미 계산된 값이면 바로 반환
    dp[x] = fib(x - 1) + fib(x - 2) # 점화식 계산, 저장, 반환
    return dp[x]
print(fib(5))

DP 문제 풀어보기

"한번에 1칸 또는 2칸의 계단을 오를 수 있을 때 N칸의 계단을 오르는 경우의 수는?"

부분문제 설정: 상태와 결과값이 정확히 대응되는 부분 문제 설정
DP(N) : N칸의 계단을 오르는 경우의 수

점화식 설정: 하위 문제를 합쳐서 상위 문제의 결과를 얻는 방법 도출
DP(N) = DP(N-1) + DP(N-2)

초기값 설정: 가장 기본적인 경우에서의 답을 미리 구해놓음
DP(1) = 1, DP(2) = 2

DP 문제 판별하기

1. 부분 문제의 답을 확정할 수 있는가?
   하위 문제의 답을 구하는데 상위 문제의 답을 활용하지는 않는가?
   (예) DP(N): N칸의 계단을 오르는 경우의 수 계단을 내려가는 경우는 없으므로 상위 문제에서 하위 문제로 돌아오지 않는다

2. 점화식에서 누락되거나 중복된 경우가 있는가?
   (예) DP(N) = DP(N-1) + DP(N-2): 1칸 또는 2칸 둘 중 하나만 선택

3. 초기값을 올바르게 구하였는가?
   (예) DP(1) = 1, DP(2) = 2 > 직접 계산해서 확인

백준 풀어보기

백준 #9252

문제: 두 수열이 주어졌을 때, 최장 공통 부분수열을 구한다
(예) ACAYKP와 CAPCAK의 최장 공통 부분수열은 ACAK

부분문제 설정

dp[i][j]: s의 i번째 문자, t의 j번째 문자까지 봤을 때 LCS의 길이
(예) dp[4][3] = 2

하위 문제로 나누기

첫번째 경우

1. s의 i번째 문자와 t의 j번째 문자가 같다
   s의 (i-1)번째 문자와 t의 (j-1)번째 문자의 DP값은 X보다 1 작음 (=X-1)
   s의 (i-1)번째 문자와 t의 j번째 문자의 DP값은 X보다 1 작음 (=X-1)
   s의 i번째 문자와 t의 (j+1)번째 문자의 DP값은 X보다 1 작음 (=X-1)

점화식 도출
if S(i) == T(j), DP(i, j) = DP(i-1, j-1) + 1
else DP(i, j) = max(DP(i-1, j), DP(i, j-1))

경로 역추적

• DP 테이블 값에 영향을 준 하위 문제 기록
• S(i) == T(j)일 때 `(i-1, j-1)
• S(i) != T(j)일 때, DP(i-1, j), DP(i, j-1) 중 큰 것의 인덱스
• 상위 문제에서 하위 문제로 돌아가면서 경로 복원

s = input()
t = input()

n = len(s)
m = len(t)
dp.= [[0 for i in range(m+1)] for i in range(n+1)]
prev = [[0, 0] for i in range(m+1)] for i in range(n+1)]

for i in range(1, n+1):
	for j in range(1, m+1):
    	if s[i-1] == t[j-1]:
        	dp[i][j] = d[i-1][j-1] + 1
            prev[i][j] = [i-1, j-1]
        else:
        	if dp[i-1][j] > dp[i][j-1]:
            	dp[i][j] = dp[i-1][j]
                prev[i][j] = [i-1, j]
            else:
            	dp[i][j] = dp[i][j-1]
                prev[i][j] = [i, j-1]

LCS 복원하기

lcs = ""
x = n
y = m
while x != 0 and y != 0:
	x_next = prev[x][y][0]
    y_next = prev[x][y][1]
    if x_next + 1 == x and y_next + 1 == y:
    	lcs = s[x-1] + lcs
    x = x_next
    y = y_next
print(lcs)

백준 #1520

내리막길

• DP 테이블 채우는 순서?
• dp[1][2] = dp[1][1] + dp[2][2]
• dp[2][2]를 채우기 전에 dp[1][2]를 채워야 함

Top-down DP

def fib(x):
	if x == base_case:
    	pass # 초기값 저장, 반환
    if dp[x] != -1:
    	pass # 이미 계산된 값 반환
    # dp 테이블 채우기
 	return dp[x]

부분문제 설정: dp[i][j]: (i, j)에서 출발하는 경로의 개수
점화식 설정: (i, j)에서 출발하는 경로의 개수의 합
초기값 설정: dp[n][m] = 1 - (n, m)은 종착점: (n, m)에서 (n, m)으로 가는 방법은 하나

n, m = map(int, input().split())
a = []
for _ in range(n):
	a.append(list(map(int, input().split())))

dp = [[-1 for i in range(m)] for i in range(n)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def f(x, y):
	if x == n - 1 and y == m - 1:
    	dp[x][y] = 1
        return 1
    if dp[x][y] != -1:
    	return dp[x][y]
    res = 0
    for i in range(4):
    	xx = x + dx[i]
        yy = y + dy[i]
        if 0 <= xx < n and 0 <= yy < m:
        	if a[x][y] > a[xx][yy]:
            	res += f(xx, yy)
    dp[x][y] = res
  	return res
    
print(f(0, 0))

배낭 문제

백준 #12865

N개의 물건이 있고 무게 제한이 있는 가방이 있어 물건 중 선택하여 가장 가치가 크도록 가방을 채우기

부분문제 설정:

• 각 물건을 선택하는 경우의 수는 2^N 가지
• N가지로 줄이는 방법 필요

DP(i): 1~i번 물건까지 선택 여부를 결정했을 때, 배낭 속 물건들의 가치의 최댓값

배낭에 넣을 수 있는 무게 제한 (100,000)

• DP(i, j): 1~i번 물건까지 선택 여부를 결정했고 총 무게가 j인 경우, 배낭 속 물건들의 가치의 최댓값

점화식 설정:

1~i번 물건 선택 여부 & 무게 j
-> 1~(i-1) 선택, 무게 j
-> 1~(i-1) 선택, 무게 j-wi (wi = i번째 물건의 무게)

DP(i, j) = max(DP(i-1, j), DP(i-1, j-w)+v)(j>=w)
DP(i, j) = DP(i-1, j)(j<w)

초기값 설정:

i=0일 때, 아무것도 선택하지 않았으므로 DP(0, 0) = 0
DP(0, j) = -1
i=1부터 점화식으로 구하자

메모리 제한이 없을 때 솔루션

n, k = map(int, input().split())
dp = [[-1 for i in range(k+1)] for i in range(n+1)]

dp[0][0] = 0

for i in range(1, n+1):
	w, v = map(int, input().split())
    for j in range(k+1):
    	if dp[i - 1][j] != -1:
        	dp[i][j] = dp[i - 1][j]
        if j >= w and dp[i - 1][j - w] != -1:
        	dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v)

print(max(dp[n])

메모리 8MB 제한일 때 솔루션

점화식 다시 만드기
DP(i, j) = max(DP(i-1, j), DP(i-1, j-w)+v) (j >= w)

테이블 두개만 있어도됨
dp: i의 테이블
dp_copy: i가 (i-1)이였을 때의 테이블

n, k = map(int, input().split())
dp = [-1 for i in range(k+1)]
dp[0] = 0
dp_copy = dp.copy()

for i in range(1, n+1):
	w, v = map(int, input().split())
    for j in range(k+1):
    	if dp_copy[j] != -1:
        	dp[j] = dp_copy[j]
        if j >= w and dp_copy[j - w] != -1:
        	dp[j] = max(dp[j], dp_copy[j -w] + v)
    dp_copy = dp.copy()
print(max(dp))

가장 긴 증가하는 부분 수열

백준 #11053

문제: 수열이 주어졌을 때, 순서대로 수를 몇개 뽑았을 때 증가하는 수열 중 가장 긴 것

부분 문제 설정:

DP(i): A1~Ai로 만들 수 있고 Ai를 반드시 포함하는 LIS

• Ai를 반드시 포함해야 함

점화식 설정:

DP(1)부터 DP(i-1)까지 확인한 다음
이 뒤에 Ai를 이어붙이기 (LIS 길이 1 증가)

• Ai <= Aj라면 DP(j) 뒤에 Ai를 이어붙일 수 없음
• Ai > Aj인 모든 i<=j<i에 대해 DP(j)의 최댓값을 구하고 1을 더하면 됨

최댓값이 없을 경우 최댓값은 0으로 간주

시간 복잡도: O(N^2)

n = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(n)]
dp[0] = 1
for i in range(1, n):
	for j in range(i):
    	if a[i] > a[j]:
        	dp[i] = max(dp[i], dp[j])
    dp[i] += 1
print(max(dp))

시간 복잡도를 더 작게 풀기

1. 같은 길이의 LIS 중 마지막 원소가 가장 작은 것만 남긴다
   더 큰 수 뒤에 Ai를 이어붙일 수 있으면 더 작은 수 뒤에도 이어붙일 수 있다
   가장 작은 수 뒤에 이어붙일 수 없다면 LIS를 만들 수 없다

2. 길이 i의 LIS 중 가장 작은 마지막 원소를 Bi라 하자
   이는 증가수열이다
   Bi < B(i-1)이라 가정하자
   길이 i인 LIS의 (i-1)번째 원소는 Bi보다 작다
   그 원소를 마지막으로 하는 길이 (i-1)의 LIS가 있다
   B(i-1)보다 작은 마지막 원소가 있으므로 B의 정의에 모순된다
   -> 이분탐색으로 B를 탐색하자

이분탐색

• bisect_left: 정렬된 배열에서 원하는 값 이상의 가장 작은 인덱스 반환
• bisect_right: 정렬된 배열에서 원하는 값 미만의 가장 큰 인덱스 반환
• Ai 미만의 B 중 가장 긴 LIS에 속하는 것

from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(n)]
dp[0] = 1
b = [a[0]]

for i in range(1, n):
	j = bisect_left(b, a[i])
    dp[i] = j + 1
    if j == len(b):
    	b.append(a[i])
    else:
    	b[j] = a[i]
print(max(dp))