다이나믹 프로그래밍(귀납적 해법)

https://youtu.be/5Lu34WIx2Us

영상 내용 정리

0. 기본 용어

• 다이나믹 프로그래밍 : 메모리를 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 ➕ 원래 명칭은 귀납적 해법(Inductive Solving). 세계 2차 대전 때 연구자들이 국회로부터 연구비를 받기 위해 비직관적이고 재미없는 귀납적 해법이라는 이름 대신에 다이나믹 프로그래밍이라는 이름으로 연구 계획서를 제출하면서 다이나믹 프로그래밍이라는 이름이 널리 퍼짐. 굳이 ‘다이나믹’이라는 단어를 쓴 이유는 프로그램이 실행되가면서 해답이 변하기 때문.
  
• 메모이제이션 : 이전에 계산된 값을 저장하는 행위, 캐싱이라고 부르기도 함

1. DP의 조건과 구현

• 조건
  • 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결 가능함
    • 이 조건은 부분정복법과 유사하고 실제로 점화식도 부분정복법과 비슷하게 나옴
  • 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 함
    • 이 조건이 부분정복법과 차이점
• 구현
  • 탑다운 : 해결하고자 하는 큰 문제에서 재귀를 걸어 작은 문제를 해결하고 그 결과들이 다 저장되면 답을 호출하는 방식
  • 바텀업 : 작은 문제들부터 해결하면서 답을 저장하고 큰 문제를 해결하는 방식. 보통 많이 쓰임.
  • 보통 dp 생성 → dp 초기치 초기화 → 탑다운/바텀업 구현

2. 예시 : 피보나치 수열

• 피보나치 수열은 최적 부분 구조와 중복되는 부분 문제 조건을 동시에 만족시킴
  • 최적 부분 구조 → f(6) = f(5) + f(4)
  • 중복되는 부분 문제 → f(6) = f(5) + f(4) = f(4) + f(3) + f(3) + f(2) = … = f(1) + f(1) …. + f(2) + f(2) + ….
• 코드

# 탑다운
d = [0] * 100
def f(x):
		# 재귀 종료 조건, x == 1 or x == 2
		if x == 1 or x == 2:
				return 1
		# 중복되는 부분 문제이면 스킵
		if d[x] != 0:
				return d[x]
		d[x] = f(x-1) + f(x-2)
		return d[x]

print(f(99))

# 바텀업
d = [0] * 100
d[1], d[2] = 1, 1
n = 99

for i in range(3, n+1):
		d[i] = d[i-1] + d[i-2]

print(d[n])

• 시간복잡도 차이 : 단순 재귀 → 지수 vs DP → O(N)

3. DP 접근 방법

• DP 문제는 이 문제가 DP 문제라는 사실을 모르면 문제 해결이 매우 힘들어짐
  • DP 문제는 메모리를 써야지 시간 복잡도가 지수로 안 나오는 경우가 많기 때문
• 그리디, 구현, 완전 탐색을 먼저 생각해보고 추가적으로 다른 알고리즘도 떠오르지 않으면 고려할 수 있음
• 재귀 함수로 비효율적인 완전탐색을 한 다음 DP 코드로 개선하는 방식도 가능함(탑다운)
• 보통은 전형적인 DP 문제가 출제되는 경우가 많음

💯 코테 문제 풀이

개미 전사

• 조건 검토

  • 최적 부분 구조 : dp[i] = max(dp[i-1], dp[i-2] + li[i])

    • ind i까지 가장 많이 털 수 있는 식량의 합
      

  • 반복되는 부분 문제 : dp[4] = max(dp[3], dp[2] + li[4]) = max(max(dp[2], dp[1] + li[3]), …)

• 코드 구현

  # 입력
  N = int(input())
  A = list(map(int, input().split()))
  
  # dp 생성
  dp = [0] * N # ind i까지 가장 많이 털 수 있는 식량의 합
  
  # dp 초기치 초기화
  dp[0] = A[0]
  dp[1] = max(dp[0], A[1])
  
  # 바텀업 구현
  for i in range(2, N):
  		dp[i] = max(dp[i-1], dp[i-2] + A[i])
  
  print(dp[-1])

1로 만들기

• 조건
  • 최적 부분 구조 : dp[i] = min(dp[i-1], dp[i//3], dp[i//2], dp[i//5]) + 1
    • ind i가 1이 되는데 필요한 연산 횟수 최소값
  • 반복되는 부분 문제
• 코드 구현

# 입력
N = int(input())

# dp 생성
dp = [0] * (N + 1) # ind i가 1이 되는데 필요한 연산 횟수 최소값

# dp 초기치 초기화
dp[1] = 0 # 의미는 없음

# 바텀업 구현
for i in range(2, N+1):		
		# case 1 : X - 1 
		dp[i] = dp[i-1] + 1

		# case 2~4 : X//2, X//3, X//5
		if i%2 == 0:
				dp[i] = min(dp[i//2] + 1, dp[i])
		if i%3 == 0:
				dp[i] = min(dp[i//3] + 1, dp[i])
		if i%5 == 0:
				dp[i] = min(dp[i//5] + 1, dp[i])

print(dp[N])

효율적인 화폐 구성

• 조건
  • 최적 부분 구조 : $dp[i] = min(dp[i-k_1],\ dp[i-k_2], ...) + 1$
    • ind i를 만드는데 필요한 화폐의 수의 최소값
  • 반복되는 부분 문제
• 코드 구현

# 입력
N, M = map(int, input().split())
K = [int(input()) for _ in range(N)]

# dp 생성
INF = float('inf')
dp = [INF] * (M + 1) # ind i를 만드는데 필요한 화폐의 수의 최소값

# dp 초기치 초기화
dp[0] = 0 

# 바텀업 구현 1 -> if 안에 조건문 하나 더 있는 대신 단순
for i in range(min(K), M+1):
		for ki in K:
				if 0 <= i - ki and dp[i-ki] != INF:
						dp[i] = min(dp[i], dp[i-ki] + 1)

# 바텀업 구현 2 -> 조금 더 복잡한데 속도는 더 빠름
for ki in K:
		for i in range(ki, M+1):
				if dp[i-ki] != INF:
						dp[i] = min(dp[i], dp[i-ki] + 1)

print(dp[M])

금광 (최대 경로 찾기)

• 조건
  • 최적 부분 구조
    $dp[i][j] = max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j-1]) + li[i][j]$
    - ind i, j 까지 오는 동안 모을 수 있는 황금의 최대값
    - 원하는 답 : $max(dp[:][j])$
  • 반복되는 부분 문제
• 아이디어

  1	3	3	2	10
  2	1	4	1	1
  0	6	4	7	1

  1	5	8	14	24
  2	3	12	13	20
  0	8	12	19	20

• 코드 구현

for _ in range(int(input())):
		# 입력
		N, M = map(int, input().split())
		A = list(map(int, input().split()))
		

		# dp 생성
		dp = [A[i:i+M] for i in range(0, N*M-1, M)] 
		# ind i, j 까지 오는 동안 모을 수 있는 황금의 최대값
		
		# 바텀업 구현
		for j in range(1, M):
				for i in range(N):
						# 왼쪽 위에서 오는 경우
						left_up = dp[i-1][j-1] if i != 0 else 0
						# 왼쪽에서 오는 경우
						left = dp[i-1][j-1]
						# 왼쪽 아래에서 오는 경우
						left_down = dp[i+1][j-1] if i != N-1 else 0
						
						dp[i][j] = dp[i][j] + max(left_up, left, left_down)
		
		print(max([dp[-1][j] for j in range(M)]))

• 장애물이 있는 경우 NONE 값을 이용해서 스킵할 수 있다
• 최대 경로를 찾는 방법은 dp 최대값에서 A 값을 이용해서 거슬러가면 된다

1	3	3	💩	10
2	1	4	1	1
0	💩	4	7	1

1	5	3	💩	10
2	3	4	1	1
0	💩	4	7	1

• 2차원 격자가 아닌 지형에서 탐색은 BFS로 구현하는게 좋다

병사 배치하기(LIS; Longest Increasing Subsequence)

• 조건

  • 최적 부분 구조
    $dp[i]= max(dp[i], dp[j] + 1)\ where\ j<i\ \&\ li[j] < li[i]$
    - li[i]를 마지막 원소로 가지는 증가 부분 수열의 최대 길이
    - 원하는 답 : $max(dp)$
  • 반복되는 부분 문제

• 아이디어

  li	4	2	5	8	4
  i = 0	1	1	1	1	1
  i = 1	1
  i = 2	1(4)	1(2)
  i = 3	1	1	2
  i = 4	1	1	2	3
  i = 5	1	1	2	3	2

• 코드 구현

# 입력
N = int(input())
A = list(map(int, input().split())))
A.reverse() # 문제를 LIS 문제로 치환하기 위해

# dp 생성
dp = [1] * N # li[i]를 마지막 원소로 가지는 증가 부분 수열의 최대 길이

# dp 초기치 초기화
# 의미 없음

# 바텀업 구현
for i in range(1, N):
		# 조건 1 : j < i
		for j in range(i):
				# 조건 2 : li[j] < li[i]
				if A[j] < A[i]:
						dp[i] = max(dp[i], dp[j] + 1)

print(N - max(dp))