다이나믹 프로그래밍

다이나믹 프로그래밍은 메모리를 적절히 사용해 시간 효율성을 비약적으로 향상시킬 수 있는 방법이다. 동적 계획법이라고도 한다. 이미 계산된 결과를 저장해두어 다시 계산하지 않도록 한다. 일반적으로 Top-down(하향식), Bottom-up(상향식) 두 가지 방식으로 구분된다.
전형적으로 Bottom-up 방식의 활용이 더 많다.

보통 아래와 같은 두 가지 사용조건을 만족할 때 사용한다.

1. 최적부분 문제구조(Optimal Substructure)

• 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 때

2. 중복되는 부분문제(Overlapping Subproblem)

• 동일한 작은 문제를 반복적으로 해결해야 할 때

ex) 피보나치 수열

• 단순 재귀로 구현했을 때

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

이 때의 시간복잡도는 O(2N)이 된다.

• 다이나믹 프로그래밍으로 구현했을 때 (Top-down)

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

위의 다이나믹 프로그래밍처럼 메모이제이션(Memoization)을 이용해 구현했을 시, 시간복잡도는 O(N)이다.

• 다이나믹 프로그래밍으로 구현했을 때(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])

- 메모이제이션(Memoization)

한번 계산한 결과를 메모리 공간에 메모해두는 기법으로 캐싱(Caching)이라고도 한다. 이는 탑-다운 방식이다.

결과 저장용 리스트는 DP 테이블 이라고 부른다.