2748번: 피보나치 수 2

동적계획법 (Dynamic Programming)

피보나치 수열을 구하는 문제는 동적계획법으로 풀 수 있는 대표적인 문제입니다. 동적계획법은 작게 쪼개서 작은 문제의 답을 구하고 그 답을 바탕으로 더 큰 문제의 답을 구해가는 문제해결법입니다.

메모이제이션

작은 부분의 답을 구했으면 그 답을 메모리에 저장하고 더 큰 문제의 답을 구할 때 가져다 쓰는 방법입니다. 작은 문제로부터 큰 문제로 나아가므로 bottom-up 방식이라고도 합니다.

let n = Int(readLine()!)!

// 이미 구한 피보나치 수열을 저장할 배열 만들기 (n + 1의 크기만큼)
var cache = Array(repeating: -1, count: n + 1)

// 피보나치 수열의 초기값
cache[0] = 0
cache[1] = 1

// 이전에 구한 수를 이용해서 다음 수를 구한다 (ex. 0과 1을 이용해서 2의 수를 구한다)
for i in 2..<(n + 1) {
    cache[i] = cache[i - 2] + cache[i - 1]
}

print(cache[n])

재귀함수

큰 문제를 구하기 위해 그 문제를 쪼개서 구하는 방법입니다. 큰 문제에서 작은 문제의 방향으로 나아가므로 top-down 방식이라고도 합니다.

func fibo(_ n: Int) -> Int {
    if n <= 1 { return n } //👉 0과 1의 경우 그대로 0, 1을 리턴
    
    return fibo(n - 2) + fibo(n - 1) //👉 이전 2개의 수의 합
}

print(fibo(Int(readLine()!)!))

재귀함수를 구현할 때 주의할 점!

🚫  실제로 위 코드를 제출해보면 시간초과가 납니다.

피보나치 수열을 구할 때 재귀함수를 사용하면 중복되어 호출하는 함수가 너무나 많습니다. 예를 들어 n이 100이라고 하면 f(99) + f(98)로 나누어지는데 f(99)과 f(98)를 구하기 위해서 호출하는 함수들의 거의 중복됩니다. f(99)과 f(98) 역시도 두 개의 함수의 합으로 분리되므로 중복호출하는 함수는 계속 누적됩니다.

따라서 재귀함수를 사용할 때도 메모이제이션을 함께 활용하는 것이 좋습니다.

let n = Int(readLine()!)!
var cache = Array(repeating: -1, count: n + 1)
cache[0] = 0
cache[1] = 1

func fibo(_ n: Int) -> Int {
    if cache[n] < 0 {
        cache[n] = fibo(n - 2) + fibo(n - 1)
    }
    
    return cache[n]
}

print(fibo(n))