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) 에서 일부를 발췌했습니다.