[알고리즘] Dynamic programming (동적 계획법) 완전정복 with Python

동적 계획법 - 주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 또 여러 개의 소문제로 분할 가능하다. 각 소문제는 원래 주어진 문제와 동일한 문제이지만 입력의 크기가 작다. 

여러 개의 소문제로 분할하여...??? 응??

DP를 처음 공부하신다면 이게 무슨 말이지? 이해가 잘 안 가실 수 있으실 텐데요. 그래서 하나의 좋은 예시가 있습니다 ㅎㅎ

바로 피보나치 수열인데요. 피보나치 수는 1, 1, 2, 3, 5, 8... 로 다음과 같은 점화식으로 나타낼 수 있습니다.

 

이제 이런 피보나치 수열을 다음과 같이 분해해서 트리 형태로 나타내 보면, 소문제가 상위 문제를 해결하기 위해 사용되는 것을 볼 수 있습니다. 이 말이 즉, 위에서 설명한 "여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결" 부분이라 할 수 있습니다. 

 

다만 한가지 문제점이 있는데요. 소문제의 결과가 상위문제의 결과를 찾는 데 사용됨으로 각각의 소문제는 중복될 수가 있습니다. 이렇게 되면 같은 소문제를 여러 번 반복해 계산하다 보니 자원낭비가 심하겠죠? 당연히 시간도 더 걸리구요.

그래서 동적 계획법은 소문제의 해를 따로 저장해놓고 이를 더 큰 문제를 푸는데 이용합니다. 한 번 푼 문제는 다시 풀지 않고 저장해둔 값을 사용함으로써 자원 절약과 시간 절약을 하는 거죠 ㅎㅎ

 

참고로 분할 정복, 탐욕법과의 차이를 잠깐 집고 넘어가자면, 

분할 정복의 경우 소문제가 독립적이고, 동적 계획법은 소문제가 독립적이지 않습니다. 대표적인 분할정복 방법을 사용한 퀵 정렬, 병합 정렬을 떠올려 보세요. 각각 분할했던 원소들이 정렬 과정에서 다른 원소에 영향을 끼치거나 그런게 아니잖아요? 

하지만 피보나치 수열만 보더라도 동적 계획법 적용이 가능한 문제는 소문제가 상위 문제에 사용됨으로 영향을 끼치게 됩니다. 즉 독립적이지 않다는 것이죠. 

 

동적 계획법과 탐욕법과의 차이는 탐욕법의 경우 각 단계별로 현재 상태에서 가장 최적의 경우를 판단해서 결정하기 때문에, 문제에 따라 최적해를 구할 수도 그렇지 않을 수도 있습니다. 하지만 동적 계획법의 경우 모든 가능성을 고려하므로 어떤 문제든 항상 최적의 결과가 도출됩니다. 

 

다시 돌아와서! 아까 동적 계획법은 소문제의 해를 따로 저장해서 나중에 다시 사용한다고 했는데요. 이렇게 중복 연산을 방지하는 방법에는 두 가지 방법이 있습니다.

 

1. 메모이제이션(하향식)

하향식(Top-Down)은 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어 나가는 방법입니다. 흔히 메모이제이션이라고 부릅니다. 

# DP 
# memoization (하향식)

dp = [0]*100 # 소문제 결과를 저장할 리스트
dp[0] = 1 
dp[1] = 1

def fib(n):
    
    # 만약 계산한 적이 없다면 재귀로 계산 
    if dp[n] == 0:
        dp[n] = fib(n-1) + fib(n-2)
    
    # 있다면 그대로 반환 
    return dp[n]

fib(10)

 

2. 타뷸레이션 (상향식)

상향식(Bottom-Up)은 더 작은 하위 문제부터 살펴본 다음 작은 문제의 정답을 이용해서 큰 문제의 정답을 풀어나가는 방법입니다. 흔히 타뷸레이션이라고 부릅니다. 

# DP
# 타뷸레이션 (상향식)

def fib(n):

    dp = [0]*(n+1)
    dp[0] = 1
    dp[1] = 1
    
    # 작은 값(소문제)부터 직접 계산하며 진행 
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

fib(10)

 

그럼 동적 계획법은 어떤 문제에 적용해야 할 까요? 

어떤 문제를 보고 우선 이 문제가 최적성의 원리를 만족하는지 판단해야 합니다. 여기서 최적성의 원리란 주어진 문제의 부분해가 전체 문제의 해를 구하는데 사용되는지를 의미합니다. 동적 계획법은 소문제의 결과를 다른 소문제를 푸는 데 사용하니까 당연한 얘기죠?

만약 최적성의 원리가 적용됨을 확인했으면 주어진 문제를 소문제로 분해하여 최적해를 제공하는 점화식을 도출해야 합니다. 이제 이 점화식을 코드로 옮겨 작성하면 되는데요. 

가장 이해하기 쉬운 것이 문제를 풀면서 살펴보는 거니까 다른 DP문제 하나를 더 풀어봅시다 ㅎㅎ

Q1. Leetcode (leetcode.com/problems/climbing-stairs/)

계단을 오를 때 한 칸 혹은 두 칸씩 올라갈 수 있다고 가정했을 때 계단 꼭대기까지 올라가는 방법의 수를 구하는 것이 문제입니다. 

이 문제의 점화식은 어떻게 될까요? 

1 계단: 1

2 계단: 1+1, 2

3 계단: 1+1+1, 1+2, 2+1

4 계단: 1+1+1+1, 2+2, 2+1+1, 1+1+2, 1+2+1

......

3계단을 올라갈 때는 2계단을 오른 후 1계단을 오르거나 1계단을 오르고 2계단을 오르는 경우를 더해주면 됩니다.

4계단을 올라갈때 역시 3계단을 오른 후 1계단을 오르거나 2계단을 오르고 2계단을 오를 때의 경우를 더해주면 되죠.

이전에 구했던 부분해를 전체 문제의 해를 구하는 데 사용함으로 최적성의 원리를 만족합니다.

이를 점화식으로 나타내면, n > 2 일 때, C(n) > C(n-1) + c(n-2)로 나타낼 수 있습니다. 

처음 두 항이 숫자가 달라서 그렇지, 피보나치 수하고 점화식이 똑같죠?

def climbStairs(n: int) -> int:
    c = [0]*(n+1)
    c[0] = 1
    c[1] = 2

    if n < 3:
        return c[n-1]

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

    return c[n-1]

climbStairs(5)

 

이렇듯 문제를 푸실 때 최적성의 원리를 만족하는지 확인 후, 점화식을 도출해서 문제를 푸시면 됩니다. 사실 피보나치 수나 계단 오르기 등의 문제는 정말 쉬운 문제에 속하고 다른 동적 계획법 문제들의 경우 정말 어려운 문제들이 많기 때문에 다른 문제들을 많이 풀어보는 것을 추천드립니다!

읽어주셔서 감사합니다 :)