피보나치 수열

피보나치 수열은 0번째 항이 0, 1번째 항이 1, 그리고 그 이후의 항은 앞의 두 항의 합인 수열을 말한다.
점화식으로 살펴보면 다음과 같다.

$$
F_0 = 0, F_1 = 1, F_{n+2} = F_{n+1} + F_n (n \geq 0)
$$

피보나치 수열의 n번째 항을 구하는 방법은 여러 가지가 있는데 그 중 3가지를 살펴볼 것이다.

1. 반복
2. 재귀함수
3. 메모이제이션

 

반복

def fibo(n):
    if n <= 1:
        return n

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

 

재귀함수

재귀함수를 파이썬 코드로 구현해보면 다음과 같다.

def fibo(n):
    if n <= 1:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

 

위의 코드처럼 하면 같은 함수를 여러 번 실행하게 된다.

F(N)을 구하는 과정을 트리로 그려보면 다음 그림과 같다. 

 

 

 

깊이가 N인 트리가 그려지게 된다.

즉, 시간복잡도가 $O(2^N)$이 된다는 말이다. N이 커질수록 기하급수적으로 함수 실행 횟수가 늘어나므로 효율성 측면에서 최악이다.

 

 

메모이제이션

앞서 살펴본 재귀함수의 효율성 문제를 해결하기 위해서는 메모이제이션 기법을 사용하면 된다.

메모이제이션 기법은 한 번 계산한 값은 저장해두어서 중복되는 불필요한 연산을 막는 방법이다.

이 기법을 사용한다면 다음 그림과 같이 중복되는 연산을 제거할 수 있다.

 

코드로 나타내면 다음과 같다

 

def fibonachi(n):
    if n <= 1:
        return n
        dp = [0,1]
    for i in range(2, n+1):
                dp.append(dp[i-1]+dp[i-2])
    return dp[n]

 

이전에 저장된 값을 이용하여 불필요한 연산이 실행되는 것을 막는다.