[Algorithm] DP(Dynamic Programming, 동적 계획법)

동적 계획법(DP)란?

 

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 특정 범위까지의 값을 구하기 위해 이전 범위의 값을 활용하여 효율적으로 값을 얻는 기법이다. 이전 범위의 값을 저장(Memoization)함으로써 시간적, 공간적 효율 얻는다.

 

동적 계획법(DP)의 적용

• 주어진 문제를 부분 문제로 나누었을 때, 부분 문제의 답을 통해 주어진 문제의 답을 도출할 수 있을 때
• 부분 문제의 답을 여러 번 구해야 할 때
• 즉, 한 번 계산한 값을 다시 사용해야 할 때

Memorization

• 이전에 구해둔 값을 저장해서 중복 계산을 방지
• 이전 범위의 답을 구하면, 바로 배열에 저장해 놓자!
• 시간과 공간면에서 모두 효율적!

방법

• 탑다운(하향식) 방식 : 큰 문제를 해결하기 위해 작은 문제 호출
• 보텀업(상향식) 방식 : 작은 문제부터 차근차근 도출

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP테이블'이라고 부른다. 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다. 

시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기에 보텀업 방식으로 구현하는 것을 권장한다.

 

재귀 함수로 구현

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

 

재귀 함수 + 탑다운 다이나믹 프로그래밍

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