다이내믹 프로그래밍이란? (2) 상세

보편적 의미는 '문제의 일부분을 풀고 그 결과를 재활용하는 방법' 

하나의 문제를 중복되는 서브문제로 나누어 푸는 방법

 

DP와 분할정복의 차이점

DP는 문제를 분할하는 경우 중복되는 서브문제가 있고, 분할정복은 분할된 서브문제가 독립적
DP는 서브문제가 같은 경우에 메모이제이션을 활용하여 같은 문제에 대해 해결할 수 있고,
분할정복은 서브문제가 다르기 때문에 메모이제이션을 활용하지 않는다.

다이나믹 프로그래밍

- (1) 중복된(반복되는) 서브문제 (Overlapping Subproblems)

        : 메인과 서브문제를 같은 방법(반복)으로 해결할 수 있어야 한다.(문제해결관점)
- (2) 최적 부분 구조 (Optimal Substructure)
        : 메인문제 해결방법을 서브문제에서 구하여 재사용하는 구조여야 한다.(문제의 구조관점)

다이나믹 프로그래밍의 방법론

- (1) 메모이제이션(하향식방법) : 메인문제를 분할하면서 해결을 하는 법
- (2) 태뷸레이션(상향식방법) : 가장 작은 문제를 먼저 해결하고 최종적으로 메인문제를 해결하는 법

 

---

# 예시1

# 피보나치 수열

# 재귀를 활용하는 다이나믹프로그래밍

def fib(n):
  if n < 3:
    return 1
  else:
    return fib(n-1)+fib(n-2)

fib(6)


# 메모이제이션을 활용하지만 재귀는 활용하지 않는 DP

def fib_not_recur(n):
  arr = [j for j in range(n+1)]   # 메모
  if n < 2:
    return n

  for i in range(2, n+1):         # 반복
    arr[i] = arr[i-1] + arr[i-2]

  return arr[n]

print(fib_not_recur(6))

---

# 예시 2

# 숫자 2,4,6으로 특정 숫자 N을 덧셈으로 구하는 방법은 몇가지일까?

def solve(n):

#base case
    if n < 0:
        return 0
    if n == 0:
        return 1  
   
    return solve(n-2) + solve(n-4) + solve(n-6)
    
#메모이제이션 개념을 활용하였을때

dp = {} # 딕셔너리로 메모이제이션을 위한 변수선언

def solve(memo_num):

  # base case
  if memo_num < 0:
      return 0
  if memo_num == 0:
      return 1  

  # checking if already calculated
  elif memo_num in dp:
    return dp[memo_num]
 
  # storing the result and returning
  else:
    
    dp[memo_num] = solve(memo_num-2) + solve(memo_num-4) + solve(memo_num-6)
    
    return dp[memo_num]