다이나믹 프로그래밍의 기초

0. 다이나믹 프로그래밍이란

• 다이나믹 프로그래밍이란 어떤 문제를 1)여러 개의 소문제로 분할, 2)각 소문제의 해결안을 바탕으로 주어진 문제를 해결하는 방법을 말한다.
• 그 과정에서 소문제의 해를 저장해두어 한 번 푼 문제는 다시 풀지 않고 저장해둔 해를 사용하도록 한다. 그로 인해 시간과 공간을 절약하는 알고리즘이다.
• Dynamic Programming의 앞글자를 따서 DP라고 부른다.

1. 분할정복, 탐욕법과의 차이점

• 분할정복과의 차이점
  분할정복은 주어진 문제가 소문제와 독립적이다. 동적계획법은 아니다.
• 탐욕법과의 차이점
  탐욕법은 매순간 최적의 경우를 찾는다. 따라서 문제에 따라 최적의 해를 구하지 못할 수도 있다. 그러나 동적계획법은 모든 경우를 고려한다. 따라서 항상 최적의 해를 구할 수 있다.

2. 중복 연산을 방지하는 방법

• 위에 소문제의 해를 저장, 이미 푼 문제는 저장해둔 해를 사용한다고 했다.
• 즉, 중복 연산을 방지하는 방법은 다음의 두 가지로 나뉜다.
  1) Memoization (하향식, Top down)
  2) Tabulation (상향식, Bottom up)

# 1. 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] # 계산이 된 값이 있으면, 그대로 반환     


# 2. Tabulation
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]  

3. 언제 DP를 사용하는가

• 최적성의 원리를 만족할 때, DP를 사용하면 된다.
• 최적성의 원리란, 문제의 부분해가 전체 문제의 해를 구하는 데 사용되는 것을 뜻한다.

4. Staircase 예제

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

관련 게시물