[DP] Dynamic Programming 동적계획법 이란?

컴퓨터의 연산 속도는 한계가 있고, 메모리 공간도 한계가 있으니 최대한 돌려쓸 수 있는 방법이 없을까?

 

다음의 조건이 만족하면 DP로 접근해야 한다.

• 완전탐색으로 답을 찾으려는데 너무 많은 시간이 걸린다
• 재귀로 진행했을 시에 오버헤드가 났을 경우

DP로 접근해야 하는지 최종적으로 다음 조건을 판단한다

• 큰 문제가 작은 문제로 나누어진다
• 작은 문제에서 구해지는 답들이 큰 문제들의 정답 구하는데에 영향을 준다

 

DP에는 두가지 방식이 있는데 Top-Down (하향식)과 Down-Top (상향식)이 있다

트리 형식으로 생각하고 Top-Down 

피보나치 수열을 통해 한번 정리해본다

피보나치 수열

n번째 수는 n-1 번째 수와 n-2 번째 수의 합

1번째와 2번째 수는 1

 

Top-Down 하향식 방식

구해야할 답을 시작으로 해서 작은 문제로 흘러내려가서(호출하여) 결국 큰문제를 구하는 방식

1. 큰 문제의 정답을 구하기 위해 작은 문제들을 푼다
2. 작은 문제들의 정답을 구하면 메모이제이션을 통해 배열 혹은 리스트에 저장한다
3. 작은 문제의 정답이 배열 혹은 리스트에 저장되어 있다면 연산을 하지 말고 그대로 가져와 쓴다

 

dp = [0] * 1000

def pibo(x):
	if x==1 or x==2:
    	return 1
    if dp[x] != 0:
    	return dp[x]
    dp[x] = pibo(x-1) + pibo(x-2)

 

Bottom Up 방식

작은 문제부터 모두 해결한 후에 큰 문제를 한큐에 풀어버리는 방법

탑다운 방식과 달리 메모이제이션이 아닌 DP 테이블을 만들어서 작은 문제들의 정답을 저장한다

작은 문제들의 답을 모두 저장한 후에 큰문제의 답을 한번에 추출해 낸다

 

dp = [0] * 1000

dp[0] = 1
dp[1] = 1

for i in range(2, 1000):
	dp[i] = dp[i-1] + dp[i-2]

n = 999
print(dp[n])