다이나믹 프로그래밍

다이나믹 프로그래밍의 핵심

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 나누어진 작은 문제들의 결과값은 항상 같아야 한다.
3. 작은 문제들로 나누고 각 문제를 해결한 결과값을 기록하여 추후에 재사용하는 것이 핵심
4. top-down 또는 bottom-up 방식으로 구현 가능하다. (*주로 바텀업으로 구현한다.)

다이나믹 프로그래밍 문제 접근

피보나치 수열은 다이나믹 프로그래밍을 적용하기 아주 좋은 예시이다.
아래의 피보나치 수열 예시를 통해 다이나믹 프로그래밍을 적용하는 순서를 설명해보았다.

(*문제 출처: https://www.acmicpc.net/problem/2747)

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

10

예제 출력 1

55

1. DP로 풀 수 있는 문제인가 판단하기

   피보나치 수열의 경우 5번째 피보나치 수열은 4번째 피보나치 수열 결과와 3번째 피보나치 결과의 합과 같다. 이 경우, 5번째 피보나치 수열값을 구할 때 4번째 피보나치 값과 3번째 피보나치 값을 구하는 부분 문제들로 쪼갤 수 있다. 또한 부분 문제들의 결과는 항상 같기 때문에 다이나믹 프로그래밍으로 풀 수 있다는 판단을 내릴 수 있다.

2. 점화식 세우기

   큰 문제를 작은 문제로 쪼개는 과정을 식으로 표현해야 한다.

   전체 문제들과 부분 문제들이 가지는 인과관계를 파악하여 점화식을 세우는 것이 중요하다.

   피보나치 수열의 경우 n번째 피보나치 수열의 값은 n-1번째 피보나치 값과 n-2번째 피보나치 값과 동일하므로 다음과 같이 점화식을 세울 수 있다.

   F(n) = F(n-1) + F(n-2)

3. 구현

   다이나믹 프로그래밍을 구현하는 방법에는 두가지가 있다.
   하지만 실제로는 재귀의 깊이가 깊어지는 탑다운 방식보다 바텀업 방식으로 구현하는 경우가 많다. 아래는 피보나치 수열 예시를 두가지 방법으로 구현한 것이다.

• 탑다운 방식

  탑다운 방식은 문제를 해결할 때 큰 문제에서부터 작은 문제들로 나누면서 내려간다.

  재귀함수 형태로 구현되기 때문에 코드가 간결하여 가독성이 좋고 이해하기 편하다.

  하지만 재귀적으로 구현되기 때문에 재귀의 깊이가 매우 깊어질 수 있으므로 주의해야한다.

  아래는 탑다운 방식의 구현이다.

  
  import sys
  
  N = int(input())
  D = [-1]*(N+1) # 메모이제이션을 위한 리스트
  
  # fibo(0) = 0, fibo(1) = 1 이므로 미리 기록
  D[0] = 0
  D[1] = 1
  
  def fibo(n):
  	if D[n] != -1 # 기존에 계산한적이 있다면 재사용
  		return D[n]
  	
  	D[n] = fibo(n-2) + fibo(n-1) # 점화식과 재귀를 이용하여 계산한 후 기록
  	
  	return D[n] 
  
  fibo(N)
  print(D[N])

• 바텀업 방식
  바텀업 문제는 작은 문제부터 해결해가면서 점점 큰문제로 확장하며 올라간다. 주로 반복문의 형태로 구현된다. 아래는 동일한 문제를 바텀업으로 구현한 예시이다.

   
   import sys
   N = int(input())
   D = [-1]*(N+1) # 메모이제이션을 위한 리스트
  
   # fibo(0) = 0, fibo(1) = 1 이므로 미리 기록
   D[0] = 0
   D[1] = 1
  
   for i in range(2, N+1): 
       # D[1]까지는 미리 초기화해두었으므로 그 다음으로 작은 문제인 2부터 N까지 확장하며 올라간다.
       D[i] = D[i-2] + D[i-1]
  
   print(D[N])