[알고리즘] 다이나믹 프로그래밍

다이나믹 프로그래밍

한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘

• 이전에 했던 계산을 캐싱해놓고 다시 사용하면서 중복되는 연산을 줄인다.
• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
• 점화식을 찾아내고 구현하는것이 핵심

탑다운(메모제이션) 방식

큰 문제를 해결하기 위해 작은 문제를 호출하는 방식

# top-down 방식으로 구현한 피보나치 함수
d = [0] * 100

def fibo(x):
	if x == 1 or x == 2:
    	return 1
	if d[x] != 0:
    	return d[x]
	dx = fibo(x-1) + fibo(x-2)
	return d[x]

print(fibo(99))

보텀업 방식

작은 문제부터 답을 내면서 큰 문제에 접근해나가는 방식

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

참고

가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현하는것을 권장한다.재귀함수의 스택 크기가 한정되어 있을 수 있기 때문이다.