[Python] Fibonacci sequence (피보나치 수열)

• 재귀함수

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

print(fibo(3)) # 2
print(fibo(4)) # 3
print(fibo(5)) # 5
print(fibo(6)) # 8
print(fibo(7)) # 13

단점 : 엄청난 중복 호출이 존재한다.

 

• 메모이제이션(memoization)
  • 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술
  • 피보나치 수를 구하는 알고리즘에서 fibo(n)의 값을 계산하자마자 저장하면 실행시간을 줄일 수 있다.

def fibo_memoization(n):
    global memo
    if n >= 2 and len(memo) <= n:
        memo.append(fibo_memoization(n-1) + fibo_memoization(n-2))
    return memo[n]

memo = [0, 1]
print(fibo_memoization(3)) # 2
print(fibo_memoization(4)) # 3
print(fibo_memoization(5)) # 5
print(fibo_memoization(6)) # 8
print(fibo_memoization(7)) # 13

 

• 동적 계획(DP : Dynamic Programming)
  • 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
  • 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘

def fibo_dp(n):
    f = [0,1]
    for i in range(2,n+1):
        f.append(f[i-1] + f[i-2])
    return f[n]

print(fibo_dp(3)) # 2
print(fibo_dp(4)) # 3
print(fibo_dp(5)) # 5
print(fibo_dp(6)) # 8
print(fibo_dp(7)) # 13

 

• DP 구현 방식
  • recursive(재귀)
  • iterative(반복)
  • memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능 면에서 보다 효율적
  • 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문이다.