1️⃣ 문제

문제 - 피보나치 수

2️⃣ 풀이 방법 및 코드

1️⃣ 처음 풀이한 코드

레벨2 맞아?, 너무 쉬운 거 아냐!??? 하면서 자신있게 제출했지만 테케 7~14번 다 시간초과 뜸.

알아보니 이 문제는 재귀로 풀 수 있는 문제가 아니라고 한다.

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

func solution(_ n:Int) -> Int {
    return fibonacci(n) % 1234567
}

2️⃣ 최종 수정 코드

재귀로 유명한 피보나치라지만,

숫자가 크다면 중복된 계산을 할 수 있다는 단점이 있다.

이와 같은 문제점을 해결하기 위해, 중복된 계산을 하지 않고 계산된 값을 저장하고 참조할 수 있는 동적 프로그래밍으로 해결하였다.

func solution(_ n:Int) -> Int {
    var f = [0, 1]
    
    for i in 2...n {
        f += [(f[i - 2] + f[i - 1]) % 1234567]
    }
    
    return f[n]
}