[Algorithm] DP(Dynamic Programming)

DP: 동적계획법

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

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
• 구현
  • 탑다운: 하향식
    • 재귀함수 이용
    • 메모리제이션: 한 번 계산한 결과를 메모리 공간에 메모하는 기법 (캐싱)
    • 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옴 - 한 번 계산된 결과를 담아 놓기만 하고 사용안할수도 ?
      
    • 보텀업: 상향식
    • 먼저 계산한 문제를 사용
    • 반복문 사용함
    • DP테이블: 저장용 리스트
    • 조건
      • 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음
      • 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결

피보나치를 다이나믹 프로그래밍으로 생각하기

- 탑다운: 메모리제이션 
    - 미리 계산된 결과를 다 저장해둠 
    - 시간복잡도는 O(N) 


  # 리스트를 초기화: 메모리제이션 
  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\] 

- 보텀업: 반복문, 작은문제들먼저 해결하기

  # DP 테이블 초기화 
  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])

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

• 공통점: 최적 부분 구조를 가질 때 사용할 수 있음
• 차이점: 부분 문제의 정복
  • 다이나믹 프로그래밍 문제: 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복
  • 분할 정복 문제: 부분 문제가 반복적으로 계산되지 않음
    
    

다이나믹 프로그래밍 접근

• 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면 코드를 개선하는 방법으로 사용할 수 있음