- 동적 계획법이란?
Dynamic Programming으로, DP라고 많이 부르는데,
상향식 접근법으로, 가장 작은 부분의 해답을 구한 후,
이를 저장하여, 저장한 값을 이용해 상위 문제를 풀어가는 방식을 말한다.
여기서 중요한 단어는 작은 부분의 해답과 저장하여,
상위 문제를 해결 한다는 것이다.
동적 계획의 핵심은 Memoization(메모이제이션)이라는 기법인데, 동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장하여 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 한다는 말이다.
이 것에 대해 그나마 간단하게 이해할수 있도록돕는 주제가 바로 피보나치수열이다.
피보타치 수열은 아래처럼
0, 1, 1, 2, 3, 5, 8, 13 ...
이런 식으로, 가장 처음 0, 1을 제외하고
내 앞에 위치한 두 요소를 더해서 나를 만드는 것이 피보나치 수열이다.
이 수열을 살펴보면 아래와 같은 함수를 만들 수가 있다.
func fibo(_ n: Int) -> Int {
if n <= 1 { return n }
return fibo(n - 1) + fibo(n - 2)
}이렇게 수열을 표현하는 함수를 만들었는데, 만약 4번째 수를 구하기 위해 fibo함수를 사용한다면 아래와 같이 풀어낼 수 있다.
fibo(2) = fibo(1) + fibo(0) = 1 + 0 = 1
fibo(3) = fibo(2) + fibo(1) = 1 + 1 = 2
fibo(4) = fibo(3) + fibo(2) = 2 + 1 = 3다만 우리가 알고 있는 답은 fibo(1) , fibo(0) 뿐이라서 모든 경우의 수를 쪼개고 쪼개야한다 결국 fibo(4)를 구하려면 fibo(0)을 구하는 함수를 2번 중복 실행하고, fibo(1)을 구하는 함수를 3번 중복 실행하고, fibo(2)를 구하는 함수를 2번 중복 실행해야한다.
이렇게 피보나치를 쓰면 물론 매우 간단하게 구현할 수 있지만, 하나의 결과값을 도출하는 데 중복되는 값을 얻기위해 실행되는 함수가 너무 많다. (숫자가 커질 수록 프로그램 실행 속도를 떨어뜨리는 것임)
따라서, 메모이제이션을 사용하는 동적 계획법으로 다시 짜보겠다.
DP는 곧 메모이제이션이다.
즉, 가장 작은 단위부터 계산하고 저장하여, 이를 이용해서 큰 단위 값을 도출하는 것이다.
따라서 동적 계획법에선, 작은 단위를 저장할 저장공간이 필요하다.
func fibo(_ n: Int) -> Int {
var cache: [Int] = [0, 1]
for num in 2 ... n {
let this = cache[num - 1] + cache[num - 2]
cache.append(this)
}
return cache[n]
}
fibo(6)이렇게 cache라는 저장 공간을 활용해서,
가장 작은 단위인 0, 1 부터 도출되는 값을 계속 저장해 나가는 것이다.
만약 4번째 수를 구하기 위해 다음과 같이 실행하면,
4보다 작은 값들인 0, 1, 2, 3번째 값까지를 먼저 구하여 저장하고,
이 값들이 저장되어 있는 메모리를 이용하여,
2번째 index + 3번째 index의 값을 더해 구하는 것이다.
이미 저장되어 있는 값을 활용하는 것이기 때문에, 중복 실행을 할 필요가 없다.
따라서 실행 속도가 빨라진다.