[백준/Python] 10870 피보나치 수 5

[백준/Python] 10870 피보나치 수 5

정답 코드 및 설명

import sys
def fibonacci(n):
    if n == 0:
        return 0 
    if n == 1:
        return 1 
    else:
        return fibonacci(n-1) + fibonacci(n-2)

input = sys.stdin.readline
n = int(input())

print(fibonacci(n))

큰 n 값에 대해 매우 비효율적이 될 수 있다. 이는 같은 계산이 반복적으로 수행되기 때문이다. 예를 들어, fibonacci(4)를 계산하기 위해 fibonacci(3)과 fibonacci(2)를 계산해야 하며, 이 과정에서 fibonacci(2)는 두 번 계산된다. n이 커질수록 이러한 중복 계산은 기하급수적으로 증가한다.

이 문제를 해결하기 위해 다이나믹 프로그래밍 기법을 사용할 수 있으며, 이는 "메모이제이션"(memoization)이라는 형태로 구현된다. 메모이제이션은 한 번 계산한 값을 저장해 두었다가 재사용함으로써 중복 계산을 방지하여 효율성을 높인다.

하지만 여기서는 주어진 문제의 조건 하에 간단한 재귀 함수로 충분다. n이 20보다 작거나 같은 경우에는 위의 재귀 함수로도 충분히 빠르게 결과를 얻을 수 있다.