[Coding Test][Python] Dynamic Programming(DP) 개념 및 예제

 

 

※ Dynamic Programming(DP, 동적 프로그래밍) 란?

DP는 큰 문제를 작은 문제로 나누고, 작은 문제의 결과를 재사용하여 큰 문제를 해결하는 알고리즘이다. 즉, 동일한 하위 문제가 반복되는 문제에서 효율적이다.

 

DP 주요 개념

• Optimal Substructure(최적 부분 구조)
  • 문제를 작은 하위 문제들로 나눌 수 있으며, 하위 문제의 최적 해를 사용하여 전체 문제의 최적 해를 구할 수 있어야한다.
  • ex) 피보나치 수열 : $F(n) = F(n-1) + F(n-2)$
• Overlapping Subproblems(중복 부분 문제)
  • 동일한 하위 문제가 여러번 반복해서 나타나는 경우, 이를 저장해 재사용하면 계산량을 줄일 수 있다.
  • ex) 피보나치 수열의 $F(5)$를 계산할 때 $F(4), F(3)$을 여러번 중복 계산된다.
• Memoization(메모이케이션) 
  • 이미 계산한 값을 저장해 두고, 이후에 같은 값을 다시 계산하지 않도록 하는 방식
  • Top - down 방식, 재귀 호출을 사용
• Tabulation(테이블화)
  • 하위 문제의 값을 테이블에 저장해, 작은 문제부터 차례로 계산하는 방법
  • Bottom - up 방식, 반복문 사용

DP의 작동 방식

1. 큰 문제를 작은 문제들로 나눈다(Subproblem)
2. 하위 문제의 답을 구한다
   1. 중복 계산해야하는 하위 문제가 있다(Overlapping Subproblem)
   2. 한번 계산한 결과는 저장해놓고 재계산하지 않도록 한다(Memoization, Tabulation)
3. 하위 문제에 대한 답을 통해 원래 문제에 대한 답을 계산한다.(Optimal Substructure)

DP를 사용하는 대표적인 문제

• 피보나치 수열
• Knapsack 문제
• Longest Common Subsequence(LCS)
  • 두 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제
• Minimal Cost Path
  • 2D Grid에서 시작점에서 끝점까지 이동할 때 최소 비용을 찾는 문제

DP는 점화식을 세워야하는 문제인만큼 꽤나 난이도가 높습니다.

따라서, 여러 문제를 풀어보면서 점화식을 세우는 연습을 해주시는게 좋습니다.

1. Fibonacci Problem을 통해 Top-down, Bottom - up 구현하기

1) Memoization(Top-down, 재귀 사용)

def fibo_memoization(n, memo={}):
    # Base Condition
    if n <= 1:
        return n
    # 이미 계산한 값이 존재하기 때문에 중복 계산 X
    if n in memo:
        return memo[n]
    # 상위 문제에서 하위문제로 재귀적으로 들어가면서 해결한 하위문제를 저장해놓고 사용한다.
    memo[n] = fibo_memoization(n-1, memo) + fibo_memoization(n-2, memo)
    return memo[n]

fibo_memoization(7)

13

2) Tabulation(Bottom-up, 반복문 사용)

def fibo_tabulation(n):
    if n <= 1:
        return n
    # DP Table 선언
    dp = [0] * (n+1)
    # 초기값 정의
    dp[1] = 1
    # 하위 문제의 값을 통해 상위 문제를 해결결 
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
        
    return dp[n]
fibo_tabulation(7)

13

 

2. DP 예제

Leet Code에 있는 Min Cost Climbing Stairs 예제입니다. (Min Cost Climbing Stairs - LeetCode)

 

계단을 올라갈 때 1칸 또는 2칸을 올라갈 수 있다.

계단을 밟았을 때 지불해야 하는 비용을 나타내는 배열 Cost가 주어질 때, 계단의 꼭대기에 도착하기 위해 지불해야 하는 비용의 최솟값을 구하여라 .

처음 시작은 0번째 혹은 1번째 계산에서 시작할 수 있다.

 

제약조건

2 <= cost.length <= 1000        
0 <= cost[i] <= 999

Input & Output

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6

1) Top - Down

memo = {}
def min_cost_memo(n):

    if n == 0 or n == 1:
        return 0

    # 2칸 올라가는 Cost의 합 vs 1칸 올라가는 Cost의 합
    if n not in memo:
        memo[n] = min(min_cost_memo(n-2) + cost[n-2],  min_cost_memo(n-1) + cost[n-1])

    return memo[n]
    
min_cost_memo(len(cost))

6

2) Bottom - Up

def min_cost_table(cost):
    # +1 을 해주는 이유 : 마지막 층에서 밟고 올라오는게 포함이 되지 않는다
    n = len(cost)
    dp = [0] * (n + 1)

    dp[0], dp[1] = 0, 0

    # 2칸 올라가는 Cost의 합 vs 1칸 올라가는 Cost의 합
    for i in range(2, n+1):
        dp[i] = min(dp[i-2] + cost[i-2] , dp[i-1] + cost[i-1])

    return dp[n]
    
min_cost_table(cost)

6