동적 계획법 (다이나믹 프로그래밍, DP)

동적 계획법 (다이나믹 프로그래밍, DP)❓

이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
→ 수행 시간 효율성 비약적 향상

---

사용 조건

• 최적 부분 구조
  : 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 때

• 중복되는 부분 문제
  : 동일한 작은 문제를 반복적으로 해결해야 할 때

---

구현 방법

점화식을 구하고 다음 방법 중 택 1

탑다운(하향식)

• 재귀 함수를 이용하여 구현.
• 큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출하여 작은 문제가 모두 해결되었을 때 큰 문제에 대한 답을 얻을 수 있음.
• 메모이제이션 (Memoization)
  • 한 번 계산한 결과를 메모리 공간에 메모하는 기법
  • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴
  • 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 함
  • DP에 국한된 개념은 아님

보텀업(상향식)

• 다이나믹 프로그래밍의 전형적인 형태
• 반복문을 이용하여 구현
• 아래쪽에서부터 작은 문제들을 하나씩 해결해 나가면서 먼저 계산했던 문제들의 값을 활용하여 다음 문제까지 차례대로 해결

---

대표 문제

피보나치 수열
1 1 2 3 5 8 13 21 34 55 89

점화식

an = an-1 + an-2 (a1 = 1, a2 = 1)

(1) DP 사용 X

: f(2)가 여러 번 호출 됨 (중복되는 부분 문제)

시간복잡도 : O(2N)

def fibo(n):
  if n == 1 or n == 2:
    return 1
  return fibo(n-1) + fibo(n-2)

print(fibo(6)) # 8

(2) DP : 탑다운

시간복잡도 : O(N)

d = [0] * 100

def fibo(n):
  if n == 1 or n == 2:
    return 1
  if d[n] != 0:
    return d[n]
  d[n] = fibo(n-1) + fibo(n-2)
  return d[n]

print(fibo(99)) # 218922995834555169026

(2) DP : 보텀업

d = [0] * 100
d[1] = 1
d[2] = 1
n = 99

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

print(d[n])  # 218922995834555169026

---

vs 분할 정복

공통점: 최적 부분 구조를 가짐 (큰 문제를 작은 문제로 나누고, 작은 문제들의 답을 모아 큰 문제 해결)
차이점: 부분 문제의 중복

• DP는 각 부분 문제들이 서로 영향을 미치며 중복됨
• 분할 정복(ex. 퀵 정렬 알고리즘)은 동일한 부분 문제가 반복적으로 계산되지 않음
  • 분할 이후에 피봇을 다시 처리하는 부분 문제는 호출되지 않음, 피봇 고정