[ Algorithm ] 피보나치수열 알고리즘 비교 (재귀, DP, 반복)

피보나치수열 알고리즘 비교 (재귀, DP, 반복) 

피보나치 수열에 많이 사용되는 알고리즘 3가지를 비교해보자 !

피보나치 수열은 첫번째와 두번째 값이 1이며 이후는 f(n) = f(n-1) + f(n-2) 점화식을 갖는다

 

피보나치 수열에 많이 사용되는 3가지 알고리즘은 재귀, 반복,  DP가 존재하는데

먼저 3가지 알고리즘의 복잡도를 비교해보면

재귀 O(2ⁿ)

DP O(n)

반복 O(n) 이다

---

재귀 & DP & 반복 차이점

일반적으로 재귀는 함수가 함수 내에서 자신을 호출하는 것으로 동일한 함수가 여러번 반복되는 것이다

DP 는 큰 문제를 작은 문제로 쪼개고 그 답을 저장해두었다가 재활용한다 

그렇기 때문에 재귀에서 동일한 문제가 여러번 반복된다는 비효율적인 부분을 DP로 해결할 수 있다

DP 로 작은 문제의 해를 메모리에 저장해두었다가 연산의 중복을 막아 실행속도를 빠르게 할 수 있다

 

반복은 주어진 조건이 참이 될 때까지 계속 반복하는 명령어 블록이다

일반적으로 반복이 재귀보다 빠르다

---

 

재귀 구현

def fib(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

0 인 경우 0 을 return 하고 재귀적으로 호출하여 이전 값과 이전의 전 값을 더해준다

 

DP 구현

재귀 함수 구현의 단점을 보완할 메모이제이션 방법으로 중복된 계산을 피할 수 있다

# memoization
dp = [0]*100
dp[0] = 0
dp[1] = 1
dp[2] = 1

def fib(n):
    if dp[n] == 0:
        dp[n] = dp[n-1]+dp[n-2]
    return dp[n]

단어 그대로 메모해두었다가 호출이 있을때마다 그대로 불러오는 것으로

연산을 두 번 이상 할 필요가 없어 시간이 줄어들게 된다

 

반복문 구현

가장 기본적이고 가장 효율적인 방법이다

def fib(n):
    curr, next = 0, 1
    for _ in range(n):
        curr, next = next, curr + next
    return curr

0 으로 시작하고 반복문이 실행될 때 마다 curr 값이 next 로 변경되며 next 는 curr + next 합으로 변경된다

 

정리하면 재귀가 무작정 나쁘다는 것은 아니다

재귀는 100번째를 예로 들면 시간복잡도가 기하급수적으로 증가한다

이런 경우 외에 조건이나 상황을 잘 고려해서 재귀를 사용하면 괜찮다 ^^