Dynamic Programming (with Fibonacci sequence(using Swift and Cache))
안녕하세요, 오늘은 Dynamic Programming 에 대해서 다루고자 합니다. Dynamic Programming 에서는 Divide & Conquer 과 같이 덩어리를 조각조각 내어 해를 구합니다. 하지만 둘 사이 가장 다른 점은 그 조각조각의 연관성이라 할 수 있겠습니다. 나눈 것들이 서로 관련이 전혀 없을 때 Divide & Conquer 을, 관련이 있어서 이전에 구한 값을 활용하면서 해를 구할 때 Dynamic Programming 을 활용한다고 할 수 있겠습니다. 나눈 부분들이 서로 관련이 있는데도 Divide & Conquer 방식으로 해결하고자 하면 Dynamic Programming 방식보다 더 비효율적일 가능성이 매우 높겠죠 ? 이번 글에서는 Fibonacci Sequence 를 여러가지 방식으로 해결하면서 이번 주제를 더 상세히 설명하고자 합니다.
Fibonacci Sequence
Dynamic Programming 을 다루기 전에, Fibonacci Sequence 는 n 번째 수가 n-1, n-2 번째 수의 합이 되는 수를 나열한 것입니다.
수식으로 하면 아래와 같습니다.
f(n) = f(n-1) + f(n-2) (for n >= 2, n : Int )
f(n) = n ( for n == 0 || n == 1 )
0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
Divide & Conquer 방식을 이용할 때 다음과 같이해결할 수 있습니다.
func fibonacciRecursion(_ n: Int) -> Int {
return n < 2 ? n : fibonacciRecursion(n-1) + fibonacciRecursion(n-2)
}생각보다 귀엽고 간단하죠? 하지만 Time Complexity 는 그리 귀엽지 않습니다. 너무 너무 느려요.
예를 들어 10 번째 element (f(10)) 를 구할 때는 f(9), f(8) 이 필요합니다.
f(9) 를 구할 때 f(8) 과 f(7) 이 필요한데, 이 때에 이전에 구했던 값을 이용하지 않고 다시 구하기 때문에 불필요한 과정을 많이 포함하게 되는거죠.
실제로 TimeComplexity 를 구해보면 O(2^n ) 임을 알 수 있어요.
2 -> 1 + 0 2번
3 -> 2 ( 1+0 ) + 1 4번
4 -> 4 ( 2+ 3 ) + 3 -> 1 + 2 + 4 + 4 11 번
5 -> 4 + 3 -> 15번
Divide And Conquer 은 쉽게 말하면 작게 나누어서 푸는 방법을 말합니다.
작게 나눈 부분부분이 연관성이 있어도 반복해서 계산하기 때문에, 이 경우 매우 비효율적입니다. ( 서로 연관 없는 곳에 쓰세요..)
이런 경우, 문제를 어떻게 해결하면 좋을까요 ?? 반복되는 계산을 미리 다른 곳에 저장하거나 다른 방법으로 이용해서 더 빠르게 할 수는 없을까요 ??
Dynamic Programming
위 Fibonacci Sequence 는 Divide & Conquer 방식의 Recursion 을 사용하여 풀 수 있으나, 그렇게 하는 경우 O( 2^n ) 이 나오게 되었죠?. 반복되는 값들을 이용하지 않고 계속해서 새로 계산해주었기 때문에 비효율적이라는 것을 알 수 있었습니다. 하지만, Dynamic Programming 을 이용해 푸는 경우 O(n) 까지 빨라질 수 있습니다. Dynamic Programming 에서는 서로 연관된, 반복되는 instance 를 활용하기 때문에, 방식의 차이가 Time Complexity 의 차이를 낳았습니다.
위에서 잠깐 언급했지만, Dynamic Programming 은 Divide & Conquer 방식과 사용하는 경우가 다릅니다. Divide & Conquer 의 경우 나눈 후 나온 데이터가 서로 연관이 없지만, Dynamic Programming 의 경우 그렇지 않습니다. 즉, 나눈 부분부분이 서로 연관성이 있고 활용할 수 있을 때 Dynamic Programming 을 활용하고, 그렇지 않은 경우 Divide & Conquer 방식을 사용하면 좋습니다. 따라서, Divide & Conquer 은 top to bottom 으로 비유되는 데 반해 Dynamic Programming 은 bottom to top 으로 볼 수 있습니다. n+1 번째 element 를 구하기 위해 이미 구했던 n, n-1 번째 element 를 활용하기 때문이죠.
이제 Dynamic Programming 을 이용하여 더 빠르고 효율적으로 풀어보겠습니다.
이번 예제에서는 'Memoization' 을 활용합니다.
Cache Memory 를 사용하는 방식인데, 해당 방식을 사용할 경우 O(n) 으로 줄일 수 있습니다.
memoization 은 주로 컴퓨터 프로그램의 속도를 향상시킬 목적으로 쓰이는 최적화 테크닉을 말합니다.
부담되는 function 이 내놓은 결과값을 저장하고(cache) 같은 값이 필요할 때 돌려주는 방식입니다.
( Memoization 과 Memorization 생긴게 많이 비슷하죠 ? 둘다 'to remember' 를 뜻하는 라틴어 'memoro' 에서 왔대요)
방식은 다음과 같아요
var fibonacciCache = [Int: Int]()
func fibWithMemo(_ number: Int) -> Int {
if let value = fibonacciCache[number] {
return value
}
let newValue = number < 2 ? number : fibWithMemo(number - 1) + fibWithMemo(number - 2)
fibonacciCache[number] = newValue
return newValue
}먼저, global variable 로 fibonacciCache 를 저장합니다. 그 후, fibonacci(_:) function 이 호출 되었을 때 해당 값을 바꿔주면서 작업을 빠른속도로 할 수 있습니다.
실제 fibonacci function 의 parameter 로 값을 다르게 넣어주면서 함수 호출횟수를 조회해보면, 아래와 같습니다.
| parameter | fibonacci funtion 이 호출된 수 |
| 1 | 1 |
| 2 | 3 |
| 3 | 5 |
| 4 | 7 |
| 5 | 9 |
| n | 2(n-1) |
이때, 함수 호출이 끝나고 나서는 global variable fibonacciCache 의 값이 변화된 상태입니다.
추가로 Cache 를 이용한 fibonacci function 을 몇개 더 보도록 할게요! (Cache 는 헷갈리고 중요하니까..)
func fibWithMemo2(_ n: Int) -> Int {
var fibonacciCache2 = [Int: Int]()
func fibonacci(_ number: Int) -> Int {
if let value = fibonacciCache2[number] {
return value
}
let newValue = number < 2 ? number : fibonacci(number - 1) + fibonacci(number - 2)
fibonacciCache2[number] = newValue
return newValue
}
fibonacci(n)
return fibonacciCache2[n]!
}해당 fibWithMemo2 는, global variable 을 사용하지 않고, function 내에서 Cache 를 선언한 후 내부에서 빠르게 처리합니다.
global variable 을 선언하지 않기 때문에 만약 해당 기능이 이 매우 빈번하게 사용되지는 않는다고 한다면 이 함수를 더 사용할 것 같네요.
(경우에 따라 당연히 다른 방법을 사용하는게 맞겠죠?? )
func fibWithMemo3(_ n: Int) -> Int {
if n <= 1 { return n}
var fibonacciCache3 : [Int : Int] = [0:0, 1:1]
func realFib(_ input: Int) { // calculate the result of fibonacci sequence
fibonacciCache3[input] = fibonacciCache3[input - 1]! + fibonacciCache3[input - 2]!
}
for index in 2 ... n {
realFib(index)
}
return fibonacciCache3[n]!
}이번 함수는, fibWithMemo2 와 전반적으로 같고 fibonacci sequence 를 구하는 방법만 약간 다릅니다. Recursion 을 사용하지 않고 차례대로 for 문을 이용해서 구해요.
Dynamic Programming 에서는 작은 instances 를 먼저 해결하고 결과를 저장한 후, 그 값이 필요할 때면 (다시 계산하는 대신) 언제든 활용합니다. 여기서 "programming" 은 solution 들이 형성되는 array (table) 의 사용을 의미합니다. Dynamic programming algorithm 에서는 array 내에서 바닥부터 (0번째 element) solution 을 형성해 나갑니다. (bottom-up approach)
dynamic programming algorithm 개발에서의 순서는 다음과 같습니다.
1. Establish a recursive property that gives the solution to an instance of the problem.
2. Bottom-up 방식, 더 작은 문제들을 먼저 해결하는 방식으로 진행합니다.
마지막으로 정리를 하자면, Dynamic Programming 은 Divide & Conquer 방식과 사용하는 경우가 다릅니다. Divide & Conquer 의 경우 나눈 후 나온 데이터가 서로 연관이 없지만, Dynamic Programming 의 경우 그렇지 않아요. 다시 말하면, Dynamic Programming 에서는 나눈 부분부분이 서로 연관성이 있고 활용할 수 있습니다. (이 글에서는 활용을 위해 데이터를 Cache 에 잠시 저장해서 사용하였습니다.) 따라서, Divide & Conquer 은 top to bottom 으로 비유되는 데 반해 Dynamic Programming 은 bottom to top 으로 볼 수 있습니다. (Divide & Conquer 의 대표적인 예시로는 Merge Sort 가 있지요) 아래 마지막 fibonacci function 을 끝으로 글을 마치겠습니다. 읽어주셔서 감사합니다.
func fibonacciWithArray(_ n: Int) -> Int {
var array = [1,1]
if n > 1 {
while (array.count <= n) {
count += 1
array.append(array[array.count-1] + array[array.count-2])
}
return array[array.count - 1]
} else {
return array[n]
}
}사실.. fibonacci 의 경우 Recursion 대신 Array 를 통해 풀면 Cache 의 도움을 받지 않고도 아주 빠르게 해결할 수 있습니다.
(해당 글은 Dynamic Programming, Cache 를 알아보기 위해 Fibonacci 를 이용했지만.. )
출처: Richard Neapolitan. “Foundations of Algorithms." (5th) 에서 일부를 발췌했습니다.