[Algorithm] Dynamic Programming vs. Recursion

동적계획법(Dynamic programming)은 재귀구조(Recursion)와 비교해서 살펴봐야하는 방법론인데요, 사실 두 용어가 무 자르듯 딱 상호베타적으로 구분되는 것은 아닌데 좁은 의미로 사용될 때 두 가지가 어떤 차이가 있는지 살펴보겠습니다. 두 방법론 모두 부분문제의 해결책을 전체 문제의 해결책으로 활용한다는 점에서는 공통점이 있습니다. 하지만 재귀구조는 주로 Top-Down 방식으로 (특히 함수를 재귀적으로 호출하는 방식으로) 적용하는 반면 동적계획법은 Bottom-up 방식을 사용하거나 Top-Down + Memoization 결합방식을 차용합니다. 재귀구조는 같은 작업을 여러번 반복하게 될 가능성이 있어서 깊은 재귀구조에서는 stack-overflow에러가 발생할 위험이 있습니다. 

 

피보나치 수열을 푸는 코딩을 보시죠. 재귀구조입니다. 

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

print(fibonacci(6))  # 출력: 8

 

https://willrosenbaum.com/teaching/2021s-cosc-112/notes/recursive-fibonacci/

 

fibonacci(6)값을 구하기 위해서 위 그림과 같은 방식으로 연산하게 되는데 같은 것을 여러번 재차 계산하고 있는 것을 확인할 수 있습니다. 낭비죠. 

 

(Bottom-up관점에서 접근하는 좁은 의미의) 동적계획법을 사용하면 좀 더 효율적인 프로그래밍이 가능합니다. 

def fibonacci_dp(n):
    if n <= 1:
        return n
    
    # DP 테이블 초기화
    dp = [0] * (n + 1)
    dp[1] = 1
    
    # Bottom-up 방식으로 피보나치 수 계산
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

print(fibonacci_dp(6))  # 출력: 8

 

만약 굳이굳이 Top-Down 방식을 사용하고 싶다면 반복연산이 일어나지 않도록 memoization 을 해주면 됩니다. 

def fibonacci_memo(n, memo={}):
    # 메모이제이션: 이미 계산된 값이 있으면 반환
    if n in memo:
        return memo[n]
    
    # 기저 사례
    if n <= 1:
        return n
    
    # 값 계산 및 메모 저장
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(6))  # 출력: 8