다이나믹 프로그래밍

*이코테 with 파이썬 정리노트입니다.

다이나믹 프로그래밍(동적 계획법)은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

📍일반적인 프로그래밍 분야에서의 동적(Dynamic)이란?
프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법

반면 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어

다이나믹 프로그래밍의 조건

1. 최적 부분 구조
   큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결 할 수 있다.
2. 중복되는 부분 문제
   동일한 작은 문제를 반복적으로 해결해야 한다.

다이나믹 프로그래밍의 대표적인 예는 피보나치 수열

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

하지만 이렇게 단순 재귀 함수로 코드를 작성할 경우 심각한 문제가 생길 수 있다!
지수 시간 복잡도를 가지기 때문❗️fibo(6)을 호출하면 fibo(2)가 다섯번이 호출이 된다.
중복되는 부분이 생기게 되어 매우 비효율적이게 된다.

탑다운(하향식)

메모이제이션은 한 번 계산한 결과를 메모리 공간에 메모하는 기법

값을 기록해 놓는다는 점에서 캐싱이라고도 한다.

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))

보텀업(상향식)

DP테이블은 보텀업 방식에서 사용되는 결과 저장용 리스트

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식

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

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])