다이나믹 프로그래밍?

나동빈 이코테 유튜브 강의 정리

https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 

 

다이나믹 프로그래밍 DP = 동적 계획법

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록.

 

두 가지 조건 만족 시 DP 사용

- 최적 부분 구조 Optimal Substructure

큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다.

- 중복되는 부분 문제 Overlapping Subproblem

동일한 작은 문제를 반복적으로 해결해야 합니다.

 

대표 문제. 피보나치 수열

An = An-1 + An-2 ; 인접한 항들 사이의 관계식 (점화식)

# 피보나치 수열 - 재귀함수
def fibo(x):
    if x == 1 or x == 2:
    	return 1
    return fibo(x-1) + fibo(x-2)
    
print(fibo(4)) # 결과 3

재귀함수로 구현하면,

최적 부분 구조 f(4) = f(3)+f(2) 작은 문제를 모아서 큰 문제 나누기 가능 O

중복되는 부분 문제 f(2)가 계속 호출되는 문제 발생 O

 

 

탑다운 VS 보텀업 방법

메모이제이션 방법 이용 -> DP테이블 = 결과 저장용 리스트

메모이제이션 = 한 번 계산한 결과를 메모리 공간에 메모하기 = 값 기록하기 (캐싱)

 

- 탑다운 (하향식)

전형적인 형태

# 피보니치 수열 - 탑다운 DP
d = [0] * 100 # 메모이제이션 저장. 리스트 초기화

def fibo(x):
    if x == 1 or x == 2:
    	return 1
    if d[x] != 0: # 이미 계산한 적 있다면 메모이제이션에서 결과 반환
    	return d[x]
    d[x] = fibo(x-1) + fibo(x-2) # 아직 계산하지 않은 문제
    
print(fibo(99))

- 보텀업 (상향식)

# 피보니치 수열 - 보텀업 DP
d = [0] * 100 # 메모이제이션 저장. 리스트 초기화

d[1] = 1
d[2] = 1
n = 99

for i in range(3,n+1): # 보텀업 방식은 반복문으로 구현
    d[i] = d[i-1] + d[x-2]
    
print(d[n])

메모이제이션 이용하는 경우 피보나치 수열 함수의 시간 복잡도 = O(N)

 

다이나믹 프로그래밍 VS 분할 정복

공통점 : 최적 부분 구조를 가질 때 사용할 수 있다.

차이점 : 부분 문제의 중복

다이나믹 프로그래밍 : 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다

분할 정복 : 동일 부분 문제가 반복적으로 계산되지 않는다.

분할 정복의 대표 예시 = 퀵 정렬 = 기준 원소의 위치 바뀌지 않음

 

가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 해결할 수 있는지 검토 후 DP 사용

재귀 함수로 비효율적으로 완전 탐색 코딩 후 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법 사용

 

일반 코테 = 기본 유형의 다이나믹 프로그래밍 문제 출제되는 경우 많다.

 

문제 예제

# 개미 전사 답
n = int(input())
array = list(map(int,input().split()))

d = [0]*100 # N은 최대 100

# DP 보텀업
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2,n):
	d[i] = max(d[i-1],d[i-2] + array[i]) # 점화식

print(d[n-1])

 

# 1로 만들기 정답
x = int(input())

d = [0]*30001

# DP 보텀업
for i in range(2,x+1):
    d[i] = d[i-1] + 1
    if i%2 == 0:
    	d[i] = min(d[i],d[i//2] + 1)
    if i%3 == 0:
    	d[i] = min(d[i],d[i//3] + 1)
    if i%5 == 0:
    	d[i] = min(d[i],d[i//5] + 1)

print(d[x])

 

0원 -> 화폐 0개

초기화 ; 10001을 INF(무한)의 값으로 설정

N=3, M=7이고, 각 화폐의 단위가 2,3,5인 경우

화폐단위 5인 경우, 7원을 만들기 위해서는 (5칸 앞에 있는) 2원을 만드는 경우 + 5원을 하면 된다.

2원을 만들기 위한 화폐 개수는 1이었기 때문에, 2원 1개 5원 1개로 총 2개 필요하다는 것을 알 수 있다.

# 효율적인 화폐 구성 정답
# 입력 N개의 화폐단위, M원, array N개의 화폐들
n,m = map(int,input().split())
array = []
for i in range(n):
    array.append(int(input())

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
df = [10001]*(m+1) # m원 최대값 10000원이니까

# DP 보텀업
d[0] = 0 # 0원은 화폐 단위 0개
for i in range(n): # 각각의 화폐 단위 i
    for j in range(array[i],m+1): # 각각의 금액 j
    	if d[j-array[i]] != 10001:
        	# (i-k)원을 만드는 방법이 존재하는 경우
        	d[j] = min(d[j], d[j-array[i]]+1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

 

# 금광 문제 정답
for tc in range(int(input())) :  # 테스트케이스 입력
  n.m = list(map(int,input().split()))  # 행, 열
  array = list(map(int,input().split())) # 금광 array

  # m개씩 끊어서 저장한 2차원 테이블 생성
  dp = []
  index = 0
  for i in range(n):
    dq.append(array[index:index+m])
    index += m

  for j in range(1,m):
    for i in range(n):
      # 왼쪽 위에서 오는 경우
      if i == 0 : 
        left_up = 0
      else:
        left_up = dq[i-1][j-1]

      # 왼쪽 아래에서 오는 경우
      if i == n-1:
        left_down = 0
      else:
        left_down = dq[i+1][j-1]
        
      # 나머지 - 왼쪽에서 오는 경우
      left = dq[i][j-1]
      dq[i][j] = dq[i][j] + max(left_up, left_down, left) 

  # 가장 오른쪽 열에서 가장 큰 금 값 출력
  result = 0
  for i in range(n):
    result = max(result,dq[i][m-1]) 
  print(result)

 

 

# 병사 배치하기 정답1
# LIS 알고리즘 활용

n = int(input()) # 총 병사수
array = list(map(int,input().split())) # 각 병사의 전투력
# 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse()

dq = [1] * n # 열외시키지 않은 병사수
# 가장 긴 증가하는 부분 수열 (LIS) 알고리즘 수행

for i in range(1,n):
  for j in range(0,i):
    if array[j] < array[i]: # 오름차순 만족하면
      dq[i] = max(d[i],d[j]+1) #리스트 디폴트 값 1인데, 조건만족시 +1 = 2

# 열외해야 하는 병사의 최소 수를 출력
print(n-dq[n]) # 최종 값 dq[n]

# 병사 배치하기 정답2
# LIS 알고리즘 활용 X

n = int(input()) # 총 병사수
array = list(map(int,input().split())) # 각 병사의 전투력

dq = [1] * n # 열외시키지 않은 병사수
for i in range(1,n):
  for j in range(0,i):
    if array[i-1] > array[i]: # 내림차순 만족하면
      dq[i] = max(dq[i],dq[j]+1) #리스트 디폴트 값 1인데, 조건만족시 +1 = 2
    
print(n-max(dq))