[이코테] 8장 다이나믹 프로그래밍(동적 계획법)

 

 

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

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장해 다시 계산하지 않도록 해 수행 시간 효율성을 비약적으로 향상시키는 방법
• 일반적으로 Top-Down(하향식)과 Bottom-Up(상향식)으로 구성
  1. Top-Down : 재귀 함수 사용. 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출해 해결한 후, 큰 문제의 답을 얻을 수 있도록ex) Memorization 방식
  2. Bottom-Up : DP의 전형적인 형태로 리스트와 반복문 사용.
     작은 문제를 하나씩 해결해가며 리스트에 저장해 다음 문제를 해결

 

다음 2가지 조건을 만족할 때 사용 가능

1. 최적 부분 구조(Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결할 수 있음

2. 중복되는 부분 문제(Overlapping Subproblem)
동일한 작은 문제를 반복적으로 해결

 

ex) 피보나치 수열
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
피보나치 수열을 아래와 같은 점화식으로 표현 가능

 

$a_n = a_{n-1} + a_{n-2}, a_0 = 1, a_1 = 1$

 

이러한 수열을 배열이나 리스트로 표현할 수 있다.
피보나치 수열의 수학적 점화식을 프로그래밍으로 표현할 때 재귀를 쓰면 간단하다.

def fibo(x):
    if x == 1 or x == 2:  # 재귀를 멈출 수 있는 조건
        return 1
    return fibo(x - 1) + fibo(x - 2)

 

그러나 `x`가 커질수록 수행시간이 계속 증가한다. 일반적으로 \( O(2^N) \) 의 지수시간이 소요된다.
예를 들어, ` fibo(6) `을 해결하기 위해 ` fibo(2) `가 여러번 호출된다.

=> 중복적으로 문제를 풀이하고 있음. 피보나치 수열은 위의 2가지 조건을 모두 만족하기 때문에 DP방식으로 해결 가능하다.

 

---

1. Memoization 기법(하향식)

• 재귀 사용
• 큰 문제를 작게 쪼개어 저장해 해결. 한 번 구한 정보를 리스트에 저장하는 방식으로 풀이
• 값을 저장하는 방법으로 캐싱(Caching)이라고도 한다.
• 시간 복잡도가 \(O(N)\)으로 줄어듦

# 한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
# 99번째의 fibo를 구하기 위해 길이를 100으로 설정
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현(하향식)
def fibo(x):
    # 종료 조건
    if x == 1 or x == 2:
        return 1

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

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

print(fibo(99))

• 수열처럼 연속적이지 않은 경우에 사전(dict) 자료형을 이용하는 것이 유용하다.
  ex) 연속적인 $$a_0 ~ a_{n-1}$$ 모두를 구하는 것이 아닌 일부만 필요한 $$a_n$$을 계산하는 문제.

 

 

2. Bottom-Up(상향식) 방법

• 반복문 사용
• 결과를 저장하는 DP 테이블(리스트) 사용
• 작은 문제를 반복적으로 해결해 큰 문제 해결

  # DP 테이블 초기화
  d = [0] * 100
  
  # 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
  d[1] = d[2] = 1
  n = 99
  
  # 피보나치 함수를 반복문으로 구현
  for i in range(3, n + 1):
      d[i] = d[i-1] + d[i-2]
  
  print(d[n])

 

---

다이나믹 프로그래밍 VS 분할 정복

	DP	분할 정복
공통점	모두 최적 부분 구조를 가질 때 사용 가능	모두 최적 부분 구조를 가질 때 사용 가능
차이점	각 부분의 문제들이 서로 영향을 미치며 부분 문제가 중복됨	동일한 부분 문제가 반복적으로 계산되지 않음

• 최적 부분 구조란? 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 상황
• 분할 정복의 퀵 정렬은 pivot을 한 번 결정하면 그 기준 원소의 위치는 바뀌지 않음(반복적 계산X)

 

다이나믹 프로그래밍 문제에 접근하는 법

1. 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요

• 그리디, 구현, 완전 탐색 등의 아이디어로 문제 해결 가능한지 검토한 후, 다른 풀이 방법이 떠오르지 않을 때 DP를 고려
• 작은 문제를 조합해 큰 문제를 해결할 수 있는 구조가. 부분 문제가 중복되는 특성을 가짐

3. 일단 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 후, 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있을 때 코드 개선으로 사용
4. 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음