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

분할 정복 알고리즘

• 큰 문제를 한번에 해결하기 어려울 때, 여러개의 작은 문제로 나누어 해결하는 기법
• 이때 동일한 작은 문제들이 반복적으로 계산되는 경우가 생길 수 있음
• 이를 보완하기 위해 나온 방법이 다이나믹 프로그래밍

Dynamic Programming (동적계획법)

1. 의미

• 필요한 계산 값을 저장해두었다가 재사용하는 알고리즘 설계 기법
• 처음 진행되는 연산을 기록하고 이미 진행되었던 연산이라면 기록되어있는 값 호출 = 시간, 자원 절약 가능
• 모든 가능성을 고려하여 항상 최적의 결과 도출

2. 사용 조건

1. 최적 부분 구조 : 큰 문제를 작은 문제를 나눌 수 있다. 이러한 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.
2. 중복된 하위 문제 : 동일한 작은 문제를 반복적으로 해결해야 한다.

3. 구현 방식

1. Memoization (Top-Down, 하향식)

• 재귀함수를 사용해 구현하는 다이나믹 프로그래밍 방법
• 큰 문제를 해결하기 위해 작은 문제를 호출

2. Tabulation (Bottom-Up, 상향식)

• 재귀함수를 사용하지 않고 단순 반복문을 사용해 구현하는 다이나믹 프로그래밍 방법
• 하위 문제부터 시작해서 더 큰 문제를 해결
• 수열처럼 연속적이지 않은 자료가 주어질 때 유용

4. 대표적인 예 (피보나치 수열)

• Top-Down

memo = [0]*100
# 피보나치 수열을 재귀함수로 구현
def fibo(x):
  if x==1 or x==2:
    return 1

  # 이미 계산한 적있는 문제라면 그대로 반환
  if memo[x] != 0:
    return memo[x]

  # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
  memo[x] = fibo(x-1)+fibo(x-2)
  return memo[x]


print(fibo(6))

----------------------------------------------------------------------

> 8

• Bottom-Up

dp = [0]*100
# 피보나치 수열을 반복문으로 구현
dp[1]=1
dp[2]=1
n=6

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

print(dp[n])

-----------------------------------------------

> 8

참고

[Python] Dynamic Programming(동적계획법) 알고리즘
동적계획법(Dynamic Programming) 정리글_Python
[알고리즘] 다이나믹 프로그래밍 with Python