Fibonacci Series

피보나치 수열은 0과 1을 제외하고 각 항이 바로 앞의 두 항의 합으로 이루어진 수열이다.

Fibonacci in Swift

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

위 코드의 시간 복잡도는 O(2^n)으로 매우 느리고 비효율적이다. 이를 보완하기 위해서 Memoization 기법을 사용한다.

Memoization

var memo = [Int: Int]()

func fib(_ n: Int) -> Int {
    if n == 0 { return 0}
    else if n == 1 { return 1 }

    if let result = memo[n] { return result }

    memo[n] = fib(n - 1) + fib(n - 2)

    return memo[n]!
}

fib(22) // 70 max

Memoization은 계산 결과를 저장하여 속도를 빠르게 하는 최적화 기법이다. 이를 피보나치 수열에 적용하면 위와 같은 코드를 작성할 수 있다. memo라는 딕셔너리를 만들어서 피보나치 수열의 계산 결과를 그 안에 저장해 놓으면 똑같은 계산을 반복하지 않기 때문에 O(n)의 시간 복잡도를 얻을 수 있다.