동적 계획법 으로도 불린다
🙋🏻♀️ 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미일까?
자료구조에서 동적 할당(Dynamic allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법 을 의미한다.
그러나 다이나믹 프로그래밍에서의 다이나믹은 별 의미 없이 사용된 단어 라고 한다😅
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
두 가지 방식이 존재
다이나믹 프로그래밍은 아래의 2가지 조건을 만족할 때 사용할 수 있다.
최적 부분 구조 (Optimal Substructure)
중복되는 부분 문제 (Overlapping Subproblem)
따라서 보통 규칙을 잘 파악하여 dp 테이블의 점화식을 도출해내는 것이 dp의 핵심이다.
피보나치수열을 바텀업 방식과 탑다운 방식으로 각각 구현해보자
참고로 결과 저장용 리스트는 DP 테이블 이라고 불린다.
바텀업 방식
dp=[0]*100
dp[1]=1
dp[2]=1
n=99
for i in range(3,n+1):
dp[n]=dp[n-1]+dp[n-2]
print(d[n]))
탑다운 방식
dp=[0]*100
dp[1]=1
dp[2]=1
n=99
def fibo(n):
if n==1 or n==2:
dp[n]=1
if dp[n]!=0:
return dp[n]
dp[n]=fibo[n-1]+fibo[n-2]
return dp[n]
print(fibo(n)))