[Level 0 / DP] 피보나치 수열 + Swift

문제 유형: DP(Dynamic Programming)

피보나치 수열을 구할 때처럼, 처음 진행되는 연산은 기록해 두고, 이미 진행했던 연산은 기록되어있는 값을 가져온다.

피보나치 수열

피보나치 수열을 재귀 함수로 구현하면 다음과 같다. 그런데 중복해서 실행하는 부분이 많다. fibonacci(3)을 구하기 위해서는 fibonacci(1)을 두번 실행해야 한다.

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

동적 계획법으로 풀면 다음과 같다. 가장 작은 단위부터 계산하고 저장하여, 큰 단위의 값을 도출한다. 계산한 단위를 저장할 공간도 필요하다. cache에 순서대로 값을 넣는다.

func fibo(_ n: Int) -> Int {
    var cache: [Int] = [0, 1]
    
    guard n > 1 else { return n }
    
    for num in 2...n {
        cache.append(cache[num - 2] + cache[num - 1])
    }
    
    return cache[n]
}