Ch08. 다이나믹 프로그래밍

다이나믹 프로그래밍

중복되는 연산을 줄여 연산량을 효과적으로 줄이는 방법

문제 적용 조건

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함한 큰 문제에서도 동일하다.

주로 점화식을 이용하여 해결하는 방식이다. 피보나치 수열로 예시를 들어보자.

피보나치 수열은
n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수 (단, n=1,2일때의 피보나치 수는 1) 로 정의된다.

이를 재귀함수를 사용하면 다음과 같다.

피보나치 수열

재귀함수 이용 방식

def fibo(x):
	if x==1 or x==2:
    	return 1
    return fibo(x-2)+fibo(x-1)
print(fibo(4))

얼핏 보면 맞는 코드같지만, 동작과정을 살펴보면 중복되는 함수 호출이 존재한다.

그렇다면 호출한 함수를 별도의 공간에 기록해놓고, 다시는 호출하지 않도록 하면 되지 않을까? => 이것이 DP의 메모제이션

#메모제이션을 위한 리스트 초기화
d=[0]*100

def fibo(x):
 # 종료조건 (1혹은 2일때 1을 반환)
 	if x==1 or x==2:
    	return 1
    if d[x] !=0:
    	return d[x]
    d[x]=fibo(x-1)+fibo(x-2)
    return d[x]
    
print(fibo(99))

탑다운

큰 문제를 해결하기 위해 작은 문제를 호출 (위의 코드)

바텀업

작은 문제부터 차근차근 답을 도출 (아래의 코드)

d= [0]*100

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

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

예제 : 1로 만들기

문제
정수 X가 주어질 때 X에 할 수 있는 연산은 4가지이다.

1. X가 5로 나누어 떨어지면, 5로 나눈다.
2. X가 3으로 나누어 떨어지면, 3으로 나눈다.
3. X가 2로 나누어 떨어지면, 2로 나눈다.
4. X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용하여 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

코드

x=int(input())
d=[0]*30001

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

print(d[x])

예제 : 개미전사

문제
개미는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야하며, 최대한 많은 식량을 얻어야 한다. 개미 전사를 위해 식량창고 N에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오.

코드

n=int(input()) #식량 창고의 개수
arr=list(map(int,input().split())) #식량창고에 저장된 식량 개수
d=[0]*n+1 #인덱스가 i일때, 식량창고 i까지 도달했을 시 최대 식량값을 저장하는 배열
d[0]=arr[o]
d[1]=arr[1]

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