[알고리즘] 동적 계획법(Dynamic Programming) - 피보나치 수열 4가지 풀이

기본 재귀적 풀이

시간 복잡도: O(2^n)

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

fibonacci(100)

반복적 풀이

시간 복잡도: O(n)

def fibonacci(n):
    if n < 2:
        return n

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

    return b

fibonacci(100)

동적 계획법 - 반복적 풀이

Bottom-up : 작은 문제부터 차례대로 푸는 방법 (파이썬 추천)

def fibonacci(n):
    if n < 2:
        return n

    cache = [0 for _ in range(n+1)]
    cache[1] = 1

    for i in range(2, n+1):
        cache[i] = cache[i-1] + cache[i-2]
    return cache[n] 

fibonacci(100)

동적 계획법 - 재귀적 풀이

Top-down : 큰 문제를 작은 문제로 쪼개면서 푸는 방법

def fibonacci(n):
    cache = [-1 for _ in range(n+1)]

    def iterate(n):
        if n < 2:
            return n
        if cache[n] != -1:
            return cache[n]
        cache[n] = iterate(n-1) + iterate(n-2)
        return cache[n]
    
    return iterate(n)

fibonacci(100)

참고 사이트

https://velog.io/@polynomeer/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming