📌동적 계획법(Dynamic Programming, DP)

동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming)은

• 문제의 최적해가 하위 문제(sub-problem)의 최적해로 정의되며,
• 하위 문제가 중첩(overlapping)될 때

사용할 수 있는 알고리즘 기법이다.

예시로, 피보나치 수열을 재귀와 DP로 구하는 방식을 비교해보자.

---

1. 재귀

import time

#재귀 함수
def Fibonacci(n):
	if n == 1 or n == 2:
       return 1
   else:
       return Fibonacci(n-1) + Fibonacci(n-2)
       
n = 40
   
startTime = time.time()
result = Fibonacci(n)
endTime = time.time()
timeRecursive = endTime - startTime
   
print(f"Fibonacci({n}) 계산 결과")
print(f"값 : {result} / 실행 시간 {timeRecursive}초")

• 실행결과

  Fibonacci(40) 계산 결과
  값 : 102334155 / 실행 시간 29.934786319732666초

• 시간 복잡도 : O(2^n)

---

이 재귀함수가 실행되는 과정을 살펴보면, 동일한 과정을 반복한다는 것을 알 수 있다. 이로 인해 실행과정이 오래 걸리게 된다.

그런데 이 과정을 잘 살펴보니

• 같은 하위 문제(sub-problem)가 중첩되고
  ex) Fibo(n-k)가 반복됨
• 최종적인 해가 하위 문제의 해로 정의된다는 것을 알 수 있다.
  ex) Fibo(n) = Fibo(n-1) + Fibo(n-2)

즉 이 문제는 DP로 해결할 수 있다.
이제 피보나치 수열을 DP로 해결해보자.

---

2. 동적 계획법

import time

# 동적 계획법
def Fibonacci_DP(n):
    if n == 1 or n == 2:
        return 1

    fibo = [0 for _ in range(n+1)]

    fibo[1], fibo[2] = 1, 1

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

    return fibo[n]


n = 10000

startTime = time.time()
result = Fibonacci_DP(n)
endTime = time.time()
timeDP = endTime - startTime

print(f"Fibonacci({n}) 계산 결과")
print(f"값 : {result} / 실행 시간 {timeDP}초")

• 실행결과

Fibonacci(10000) 계산 결과
값 : 33644764876...(생략) / 실행 시간 0.00937342643737793초

• 시간 복잡도 : O(n)

재귀와 DP의 실행 시간을 비교해보면, DP방식이 재귀방식보다 매우 빠른 것을 알 수 있다.

---

탑다운(Top-Down)과 바텀업(Bottom-Up)

방금 전 문제의 경우, 바텀업(Bottom-Up) 접근 방식을 통해 문제를 풀었다.
DP는 주로 탑다운(Top-Down)과 바텀업(Bottom-Up) 접근방식을 통해서 문제를 해결한다.

---

1. 탑다운

탑다운은 위에서부터 아래로, 즉 큰 문제에서 시작해서 필요한 하위문제의 해를 구해가는 방식이다.

탑다운 방식의 경우, 재귀와 메모제이션(Memoization)을 활용한다.

메모제이션(Memoization) : 문제를 해결하는 과정에서 이미 계산한 결과를 저장해서 중복 계산을 방지하는 기법 중 하나

• 탑다운적 접근 방식
• 재귀 함수를 통해 구현된다.
• 문제를 해결하며 필요한 부분 문제만 계산되어 저장된다.

앞서 풀어본 피보나치 수열을 탑다운 방식으로 구현하면 다음과 같이 구현할 수 있다.

# 동적 계획법 (탑다운)
def Fibonacci_DP(n, memo = {}):
    if n in memo:
        return memo[n]

    if n <= 1:
        return n
    
    memo[n] = Fibonacci_DP(n-1, memo) + Fibonacci_DP(n-2, memo)

    return memo[n]

print(Fibonacci_DP(20)) # 출력 6765

Fibonacci_DP 함수를 통해서 위에서부터 재귀적으로 수열을 계산하면서, 계산된 결과는 memo 딕셔너리에 저장하며 중복 계산을 피하고 있다.

---

2. 바텀업

바텀업은 아래에서부터 위로, 즉 작은 하위문제에서 시작해 더 큰 문제의 해를 구성하는 방식이다.

바텀업 방식의 경우, 반복문과 타뷸레이션(Tabulation)을 활용한다.

타뷸레이션(Tabulation) : 문제를 해결하는 과정에서 이미 계산한 결과를 저장해서 중복 계산을 방지하는 기법 중 하나

• 바텀업적 접근 방식
• 반복문을 통해 구현된다.
• 모든 부분 문제를 계산해서 작은 것부터 순차적으로 저장한다.

앞서 구현한 코드를 다시 살펴보자.

# 동적 계획법 (바텀업)
def Fibonacci_DP(n):
    if n == 1 or n == 2:
        return 1

    fibo = [0 for _ in range(n+1)]

    fibo[1], fibo[2] = 1, 1

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

    return fibo[n]
    
print(Fibonacci_DP(20)) # 출력 6765

Fibonacci_DP 함수 내에서 fibo리스트의 인덱스가 1과 2일 때 값을 1로 초기화한다. (기저 조건(Base Case))
그리고 반복문을 통해 3에서 n까지 순차적으로 수열을 계산하고 fibo리스트에 저장한다.

---

정리

항목	탑다운(Top-Down)	바텀업(Bottom-Up)
구현 방식	재귀와 메모이제이션	반복문과 타뷸레이션(혹은 테이블)
메모리 사용	재귀 호출 스택 + 캐시	테이블에 모든 부분 문제 결과 저장
코드 복잡도	재귀 함수 사용으로 코드가 간결할 수 있음	반복문과 테이블 초기화 등으로 다소 복잡할 수 있음
계산 순서	필요한 부분 문제부터 재귀적으로 계산	작은 문제부터 순차적으로 계산

테이블(table) : 데이터를 구조화하여 저장하고, 효율적으로 검색하거나 참조할 수 있도록 만든 데이터 구조로,
여기선 문제를 해결하기 위해 부분 문제의 해답을 저장하는 배열 또는 리스트를 의미한다.

캐시(cache) : 데이터나 계산 결과를 임시로 저장해 두었다가 필요할 때 빠르게 꺼내 쓰는 저장소를 의미한다.

---

분할 정복(Divide and Conquer)과 동적 계획법(Dynamic Programming)

문제를 하위문제로 쪼개고, 그 하위문제의 부분해를 통해서 전체 문제의 해를 구한다는 측면에서 분할 정복(Divide and Conquer)과 동적 계획법(Dynamic Programming)은 동일하게 보이기도 한다.

하지만 접근 방식과 적용되는 문제의 특성에서 둘은 몇 가지 중요한 차이점이 있다.

divede 오타났다.

• 분할 정복(Divide and Conquer)

  • 하위 문제가 서로 독립적이며, 중복되지 않음
  • 문제를 여러 하위 문제로 분할한 후, 부분해를 결합해서 전체해를 구한다.

    예시 : 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary Search)

• 동적 계획법(Dynamic Programming)

  • 하위 문제가 중첩되며 여러 번 계산됨
  • 하위 문제의 부분해를 저장해놨다가 재사용하며 전체해를 구한다.

    예시 : 피보나치 수열, LCS(최장 공통 부분 수열), 막대 자르기 문제

---

여담

동적 계획법의 이름을 보면 동적(dynamic)이라는 말이 붙어있는데, 앞서 살펴본 것처럼, 사실 이 기법은 동적과는 거리가 멀다.
그런데도 이름이 이런 이유는, 동적 계획법의 고안자가 dynamic이란 이름이 멋져보여서 붙였기에 이런 이름으로 정해지게 되었다.