피보나치 수열

피보나치 수열은 앞의 두개의 숫자를 합한 값이 자신의 value가 되는 수열을 말한다.

 

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

 

기초적으로 이런 피보나치 수열을 푸는 알고리즘의 예로 recursive function을 쓰긴 하지만

이는 숫자가 커지면 그만큼 함수의 호출이 많아지므로 메모리가 터지는(?) 문제가 생긴다

def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

이러한 문제를 해결하기 위해 memoization 을 이용해 (캐쉬와 비슷한 개념) 푸는 접근 방법도 있다.

memo = {1:1, 2:1}
def fibonacci(n):
    if n == 0:
        return 0
    if n not in memo:
        memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]

 

사실 이러한 문제는

아주 pythonic하게 간단히 풀 수 있다.

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

 

아마 기본적인 코딩문제로 많이 사용되는 예시이니 알아두면 좋다.