Dynamic Programming, 동적 계획법

개념과 특징

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함

• 메모리를 적절히 사용하여 수행시간 효율성을 비약적으로 향상

• DP의 구현은 일반적으로 탑다운, 보텀업으로 구성

• 다이나믹 프로그래밍의 사용 조건

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

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

top-down과 bottom-up

top-down

• 메모이제이션(Memoization)

  • 한번 계산한 결과를 메모리 공간에 메모하는 기법
  • 값을 기록해 놓는다는 점에서 캐싱(Cashing)이라고도 함

• 탑다운 방식은 하향식이라고도 하며 메모이제이션 기법을 이용함

bottom-up

• 보텀업 방식은 상향식이라고도 하며 DP의 전형적인 형태임

피보나치 수열

a(n) = a(n-1) + a(n-2), a1 = 1, a2 = 1

• a(n-2)와 a(n-1)을 더했을 때 a(n)이 되는 수열

• 예시로는 1, 1, 2, 3, 5, 8, 13, 21, 34....

• 피보나치 수열을 배열이나 리스트로 표현

  def fibo(x):
    if x == 1 or x == 2:
      return 1
    return fibo(x - 1) + fibo(x - 2)
  
  print(fibo(4))

  → 이러한 방식의 피보나치수열은 시간복잡도가 O(2ⁿ)

다이나믹 프로그래밍을 이용한 피보나치 수열의 구현

1. 탑다운

   # memoization을 위한 리스트 초기화
   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))

2. 보텀업

   # 앞서 계산된 결과를 저장할 리스트 초기화
   d = [0] * 100
   
   d[1] = 1
   d[2] = 1
   n = 99
   
   # 반복문으로 피보나치함수 구현
   for i in range(3, n+1):
     d[i] = d[i - 1] + d[i - 2]
   
   print(d[n])

memoization을 이용한 경우 피보나치 수열 함수의 시간복잡도는 O(N)!!