11-1. 동적 계획법 알아보기

동적 계획법(dynamic programming)

• 봊갑한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

동적 계획법의 핵심 이론

원리 & 구현 방식

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. ⇒ 메모이제이션(memoization) 기법
4. 동적 계획법은 top-down 방식과 bottom-up 방식으로 구현 가능

예시 - 피보나치 수열

D[N] = D[N-1] + D[N-2] # N번째 수열 = (N-1)번째 수열 + (N-2)번째 수열

1. 동적 계획법으로 풀 수 있는지 확인

   • 6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 4번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있음
     • 6번째 피보나치 수열 = 5번째 피보나치 수열 + 4번째 피보나치 수열
     • 수열의 값은 항상 같기 때문에 동적 계획법으로 구현 가능

2. 점화식 세우기

   • 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 것이 필요
   • 피보나치 수열: D[i] = D[i-1] + D[i-2]

3. memoization 원리 이해하기

   • 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용하는 것

     

4. top-down 구현 방식 이해하기

   • 위에서부터 문제를 파악해 내려오는 방식
     • 주로 재귀 함수 형태로 코드를 구현함
   • 코드의 가독성이 좋고, 이해하기 편하다는 장점 존재

   ex)

   import sys
   input = sys.stdin.readline
   
   ## 입력
   N = int(input())
   D = [-1] * (N+1)
   D[0] = 0
   D[1] = 1
   
   ## 처리
   def fibo(n):
       if D[n] != -1: # 기존에 계산한 적이 있는 부분의 문제는 재계산하지 않고 리턴
           return D[n]
       # memoization: 구한 값을 바로 리턴하지 않고 DP 테이블에서 저장한 후 리턴하도록 로직 구현
       D[n] = fibo(n-2) + fibo(n-1)
       return D[n]
   fibo(N)
   
   ## 출력
   print(D[N])
   

5. bottom-up 구현 방식 이해하기

   • 가장 작은 부분 문제부터 해결하면서 점점 큰 문제로 확장해 나가는 방식
     • 주로 반복문 형태로 구현
   • 두 방식 중 좀 더 안전한 방식

   ex)

   import sys
   input = sys.stdin.readline
   
   ## 입력
   N = int(input())
   D = [-1] * (N+1)
   D[0] = 0
   D[1] = 1
   
   ## 처리
   for i in range(2, N+1):
       D[i] = D[i-2] + D[i-1] # 반복문을 이용하여 아래서부터 값을 채워가는 방식
   
   ## 출력
   print(D[N])