니트코드 9번 알고리즘 : 피보나치 함수

니트코드 링크 : 

https://neetcode.io/courses/dsa-for-beginners/9

NeetCode

 

재귀적 방법 :

# Recursive implementation to calculate the n-th Fibonacci number
def fibonacci(n):
    # Base case: n = 0 or 1
    if n <= 1:
        return n

    # Recursive case: fib(n) = fib(n - 1) + fib(n - 2)
    return fibonacci(n - 1) + fibonacci(n - 2)

 

 

반복적 방법 :

 

 

시간 복잡도 :

 

재귀적 : O(2^n)

반복적 : O(n)

 

 

백준

1788 

https://www.acmicpc.net/problem/1788

 

 

참고

피보나치 수열 알고리즘을 해결하는 5가지 방법

https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95