[백준 Python Swift] 2747번 피보나치 수

2747번 피보나치 수

• 문제바로가기

풀이 방법

• 재귀함수를 이용해도 되지만 이 문제에서는 시간초과가 난다
• Memoization을 사용하여 문제를 해결해도 된다
• 전항과 전전항을 더하여 다음항을 만드는 것이 피보나치 수열이기 때문에
• (전항, 전전항)을 나타낼 변수를 계속 앞으로 옮겨가면서 더해주면 계속해서 다음항이 나온다

풀이

Python

• 시간초과되는 풀이

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)
n = int(input())
print(fibonacci(n))

• 시간초과 안되는 풀이(1)

def fibonacci(n):
    cache = [0, 1]
    for _ in range(n-1):
        cache.append(cache[-1] + cache[-2])
    return cache[n]
n = int(input())
print(fibonacci(n))

• 시간초과 안되는 풀이(2)

def fibonacci(n):
    init_value = 0
    first = 1
    for _ in range(n):
        init_value, first = first, init_value+first
    return init_value
n = int(input())
print(fibonacci(n))

Swift

func fibonacci(_ n: Int) -> Int {
   var cache = [0, 1]
   if n != 0 {
       for _ in 0..<(n-1) {
           cache.append(cache[cache.index(before: cache.endIndex)] &+ cache[cache.index(before: cache.endIndex-1)])
       }
   }
   return cache[n]
}
let n = Int(readLine()!)!
print(fibonacci(n))

func fibonacci(_ n: Int) -> Int {
    var n = n, a = 0, b = 1
    var temp = a
    while n > 0 {
        a = b
        b = temp+b
        temp = a
        n -= 1
    }
    return a
}

let n = Int(readLine()!)!
print(fibonacci(n))