다이나믹 프로그래밍(DP)

DP(Dynamic Programming)

한 번 해결된 부분 문제의 정답을 메모리에 기록하는 방식이다. 점화식을 그대로 코드로 옮겨서 구현할 수 있다. 모든 경우에 DP를 사용할 수 있는 것은 아니며, 아래와 같은 조건을 만족할 때 사용가능 하다.

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

탑다운(Top-Down) 방식

재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방식을 탑다운 방식이라고 한다.

#한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
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)
    return d[x]
 
 print(fibo(99))

보텀업(Bottom-Up) 방식

단순히 반복문을 이용하여 소스코드를 작성하는 방식을 보텀업 방식이라고 한다.

#계산된 결과를 저장하기 위한 DP 테이블 초기화
d=[0]*100

#첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1]=1
d[2]=1
n=99

#피보나치 함수 반복문으로 구현
for i in range(3,n+1):
	d[i]=d[i-1]+d[i-2]

print(d[n])