DP (동적 계획법)

DP란?

Dynamic Programing - 동적계획법

큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말,
한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘이다.

DP는 다음의 조건을 만족할 때 사용할 수 있다

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

• 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우를 의미

2. 중복되는 하위 문제들

• 동일한 작은 문제를 반복적으로 해결해야 하는 경우

피보나치 수열

동적계획법을 쓰는 이유를 알아보기 위해 동적계획법을 적용시킬 수 있는 간단한 예인 피보나치 수열을 알아보자.

피보나치 수열의 점화식

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) if n > 1

피보나치 수열은 다음과 같은 값을 가진다.

재귀함수로 구현

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

print(fibo(5))

재귀함수를 이용해 구현했을 경우
f(n)에서 n의 값이 커질 수록 실행시간이 기하급수적으로 늘어나게 된다.

dp로 구현

n=int(input())

fibo=[0,1]
for i in range(n):
	fibo.append(fibo[i]+fibo[i+1])
	
print(fibo[-2])

반면에 dp를 이용하여 구현했을 경우
f(1)~f(n)까지의 값을 fibo배열에 하나씩 저장하면서 실행하므로
재귀함수로 구현했을 때에 비해 확연히 수행속도가 줄어들게 된다.