[알고리즘] 동적계획법(Dynamic Programming)

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제로 나누어 푸는 알고리즘입니다.

각 하위 문제는 한 번만 계산하고 그 결과를 저장하여, 동일한 하위 문제가 다시 나타날 때 재계산하지 않고 저장된 결과를 사용하는 것이 핵심입니다. 이로 인해 중복된 계산을 피할 수 있다는 장점을 가지고 있다!

---

동적 계획법의 기본 아이디어

 

• 분할 정복: 문제를 여러 하위 문제로 나눈다.
• 중복된 하위 문제: 여러 하위 문제가 여러 번 등장하는 경우가 많다.
• 최적 부분 구조: 문제의 최적해는 하위 문제의 최적해로 구성된다.
• 메모이제이션: 이미 계산한 하위 문제의 결과를 저장해 둔다.

 

동적 계획법의 구현 방식

동적 계획법은 크게 두 가지 방식으로 구현할 수 있습니다.

• 탑 다운(Top-Down)
• 바텀 업(Bottom-Up)

 

예시(피보나치 수열)

탑 다운 방식 (Top-down)

탑-다운 방식은 재귀(Recursion)를 사용하여 큰 문제를 작은 문제로 쪼개서 풀어나가는 방식입니다. 중복된 하위 문제를 만나면 그 결과를 메모이제이션(보통 배열에 저장한다)하여, 다시 계산하지 않고 저장된 값을 사용합니다.

 

피보나치 수열은 다음과 같이 정의됩니다.

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 2)

def fib(n, memo):
    if n <= 1:
        return n
    if memo[n] is not None:
        return memo[n]
    
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

n = 10
memo = [None] * (n + 1)
print(fib(n, memo))  # Output: 55

 

탑 다운 방식으로 피보나치 수열을 구현한 모습입니다.

 

이 코드는 fib(n)을 계산하기 위해 fib(n-1)과 fib(n-2)를 재귀적으로 호출합니다. 하지만 중복 계산을 피하기 위해 이미 계산된 결과는 memo 배열에 저장해 재사용합니다.

 

바텀 업 방식 (Bottom-Up)

바텀-업 방식은 작은 문제부터 차근차근 답을 구하면서, 이를 이용해 큰 문제를 해결하는 방식입니다. 재귀 호출 대신 반복문을 사용하며, 메모이제이션 대신 테이블을 채워나갑니다.

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

n = 10
print(fib(n))  # Output: 55

바텀 업 방식으로 피보나치 수열을 구현한 모습입니다.

 

이 코드는 dp 배열을 이용해 작은 문제(dp[0]과 dp[1])부터 시작해 차례차례 큰 문제(dp[n])를 해결합니다.

---

탑 다운 vs 바텀 업 차이점

 

• 재귀 vs 반복문
  • 탑 다운 방식은 재귀를 사용하여 문제를 쪼개고, 하위 문제의 답을 계산하면서 필요할 때 메모이제이션합니다.
  • 바텀 업 방식은 반복문을 사용해 작은 문제부터 순차적으로 해결합니다.
• 메모리 사용
  • 탑 다운 방식은 재귀 호출에 따른 스택 오버헤드가 있습니다.
  • 바텀 업 방식은 일반적으로 메모리 사용이 효율적이며, 스택 오버헤드가 없습니다.
• 구현 난이도
  • 탑 다운 방식은 문제를 분할하여 재귀적으로 접근하기 때문에 직관적이고 코드 작성이 비교적 간단합니다.
  • 바텀 업 방식은 전체 문제를 작은 하위 문제로 나누어 순차적으로 해결해야 하기 때문에 구현이 더 복잡할 수 있습니다.

결론

동적 계획법은 동일한 하위 문제가 반복되는 경우 매우 강력한 알고리즘 기법입니다. 탑 다운과 바텀 업 방식 중 어떤 것을 사용할지는 문제의 성질과 사용자의 선호도에 따라 다를 수 있습니다. 일반적으로 스택 오버헤드가 걱정된다면 바텀 업 방식을, 직관적이고 간단한 구현을 원한다면 탑 다운 방식을 선택할 수 있습니다.