[Swift] 4가지 방법의 피보나치 함수

1. 재귀 구조 브루트 포스

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

 

2. 탑다운(메모이제이션)

var dp = [Int: Int]()

func fib(_ n: Int) -> Int {
    if n <= 1 { return n }
    
    if dp[n] != nil {
        return dp[n]!
    }
    dp[n] = fib(n - 1) + fib(n - 2)
    return dp[n]!
}

 

3. 바텀업(타뷸레이션)

func fib(_ n: Int) -> Int {
    if n <= 1 { return n }
    
    var dp = Array(repeating: 0, count: n + 1)
    dp[1] = 1
    
    for i in 2...n {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

 

4. 두 변수만 이용해 공간 절약

func fib(_ n: Int) -> Int {
    var x = 0, y = 1
    
    for _ in 0..<n {
        let temp = x
        x = y
        y = temp + y
    }
    
    return x
}