[Baekjoon]백준 24416 알고리즘 수업 - 피보나치 수 1(브론즈 1) - Python

문제설명 1

문제설명 2

문제를 살펴보면 이전에는 피보나치 수를 해결하기 위해 재귀적으로 함수를 호출하여 해결하였다

하지만 그 방법 외에도 동적 프로그래밍을 통해 문제를 해결이 가능하기 때문에 이를 연습하기 위한 문제임을 알 수 있다

의사코드대로 코드를 작성하여 Python으로 제출을 하면 시간초과가 발생하고, PyPy3로 제출하면 제출이 성공한다

다른 분들의 코드를 살펴보니 메모리적인 측면이나 시간적으로 훨씬 유리한 방법이 존재하는 것 같아서

블로그를 찾아보니 획기적인 방법이 존재하였다

예제에서도 볼 수 있듯 코드2는 n-2만큼 실행이 되며, 재귀적으로 해결하는 것이 아니라 

두 개의 변수를 만들어 피보나치 수열을 저장하고, 서로 값을 바꾸어가며 갱신하는 방법이 더 빠르다

그렇게 하면 메모리도 적게 사용하면서 시간도 절약할 수 있다

def fib(n):
    first, second = 1, 1
    for _ in range(3, n + 1):
        first, second = second, first + second
        
    return second

def fibonacci(n):
    return n - 2
    
N = int(input())
print(fib(N), fibonacci(N))