DP(dynamic programming)와 메모이제이션, 피보나치 구현 (feat. swift)

 

Dynamic Programming : 동적 계획법

먼저 DP의 방식을 살펴보자면

복잡한 문제를 여러 개의 하위 문제(sub-problem)로 나누어서 풀고,

sub-problem으로부터 구한 해를 결합해 문제의 답을 도출하는 방식이다.

 

주로 최단 경로 문제에 쓰인다.

모든 경로에 대해 계산을 하고, 계산 결과를 별도로 저장하여

동일한 sub-problem이 중간에 들어갈 경우 계산 결과값을 불러들이는 방식을 사용한다.

따라서 중복되는 부분에 대해 계산 과정을 생략하기 때문에 sub-problem이 많아지는 경우 많은 시간을 줄일 수 있다.

그리디와 비교를 해보자면,

모든 경로에 대해 계산을 하기 때문에 그리디와 비교하면 시간은 더 오래 걸릴 수 있지만, 

문제에 대한 전체적인 최적의 답을 얻을 수 있기 때문에 더 정확하다.

 

알고리즘 문제를 풀 때

이 문제가 DP로 풀 수 있는지를 먼저 파악할 수 있다면 빠르게 해결할 수 있다.

 

 

조건은 다음과 같다.

1. 문제를 sub-problem으로 쪼갤 수 있는가? 2. sub-problem에서 구한 답으로 더 큰 규모의 problem의 답을 구할 수 있는가? 3. sub-problem들이 중복되는 부분이 있는가? (-> memoization으로 시간을 많이 단축시킬 수 있다.)

 

여기서 메모이제이션(memoization)이란 생소한 단어지만 별 거 없다.

그냥.. 계산한 결과를 저장해두고, 중복되는 부분이 있을 때 새로 계산과정을 거치지 않고 결과값을 읽어오는 것을 말한다.

 

 

DP로 접근할 수 있는 대표적인 예로 피보나치 수열이 있다.

점화식으로 나타내보면 F(n) = F(n-1) + F(n-2)이 된다.

 

1. 문제인 F(n)가 sub-problem들로 나누어진다. F(n-1) + F(n-2)

F(n-1) = F(n-2) + F(n-3) ... 으로 다시 sub-problem들로 나누어지게 되며,

2. 이 sub-problem에서 구한 답으로 그들의 상위 problem의 답을 구할 수 있다.

3. sub-problem이 중복되는 부분들이 존재한다. 1의 예만 보더라도 알 수 있다.

 

즉, 피보나치 수열은 DP로 풀 수 있는 조건을 만족하기 때문에 DP를 사용하면 많은 시간을 줄일 수 있게 된다.

 

 

- 무지성(?)으로 피보나치 수열을 만드는 경우

let n = 40

func fibonazzi (_ num:Int) -> Int {
	if num == 0 {
		return 0
	} else if num == 1 {
		return 1
	} else {
		return fibonazzi(num-1) + fibonazzi(num-2)
	}
}

print(fibonazzi(n))

 

위와 같이 작성할 수 있는데, 40까지는 나름대로? 빠르게 결과가 나오지만

n=50만 입력해도 하루종일(문자그대로가 아님) 연산한다. 매우매우 오래 걸린다.

 

 

- DP를 이용하여 피보나치 수열을 만드는 경우

let n = 50
var dp = Array(repeating: 0, count: 51)
dp[0] = 0
dp[1] = 1
for i in 2...n {
	dp[i] = dp[i-1] + dp[i-2]
}

print(dp[n])

 

DP만 사용했을 뿐인데 매우매우매우 빨라진다.

배열에 저장함으로써 중복되는 연산을 생략했을 뿐인데 수행시간이 천지차이이며, 결과 또한 정확하다.

 

끝