[Python] 알고리즘의 종류, 종류별 예제 _ 다이나믹프로그래밍 (6/7)

• 다이나믹 프로그래밍(동적 프로그래밍)
• 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과는 별도의 메모리에 저장해서 다시 계산 x
• Top-down, Bottom-up방식으로 구성
• 일반적인 프로그래밍 분야에서 동적(Dynamic)
• 자료구조에서 동적 할당(Dynamic Allocation)은 ‘프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법’을 의미 반면에 다이나믹 프로그래밍의 ‘다이나믹’은 별다른 의미 없이 사용된 단어
• 사용 조건

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

피보나치수열

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

문제점

메모이제이션(캐싱) / Top-Down

• 한번 계산한 결과를 메모리 공간에 메모하는 기법
• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
• 값을 기록해 놓는다는 점에서 캐싱이라고도 함.

다이나믹 프로그래밍

# Top-down
dp = [0] * 100
def fibo(x):
	if x == 1 or x == 2:
		return 1
	if dp[x] != 0:
		return dp[x]
	dp[x] = fibo(x - 1) + fibo(x - 2)
	return dp[x]
	
# Bottom-Up
d = [0] * 100
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])