[이코테] 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
피보나치 수열을 아래와 같은 점화식으로 표현 가능

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

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. 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음