[python/알고리즘] 두 가지 방법으로 피보나치 수열 구현하기

1. 재귀함수 이용하기

def F(k):
    if k > 1:
        return F(k-1) + F(k-2)
    else:
        return k

• 단점: 큰 값이 입력된 경우 시간 초과가 발생할 수 있다.

2. swap 이용하기

def F(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, (a + b)
    return a

• 0, 1을 시작으로 n만큼 for문을 돌면서 직전 두 수의 합을 새로 할당한다.