다이나믹 프로그래밍 (DP)

필요한 계산 값을 저장해두었다가 재사용하는 알고리즘 설계 기법으로, 큰 문제를 한번에 해결하기 어려울 때, 여러개의 작은 문제로 나누어 푸는 ‘분할 정복’ 알고리즘이 있다. 이때 동일한 작은 문제들이 반복적으로 계산되는 경우가 생길 수 있다. 그 문제를 매번 재계산 하지 않고 값을 저장했다가 재사용하는 기법이 바로 다이나믹 프로그래밍이다. 메모리 공간을 약간 더 사용하여 시간을 획기적으로 줄일 수 있는 방법이다.

• 다음 조건 만족 시 사용할 수 있음:
  • 최적 부분 구조
  • 중복 하위 문제
• Topdown (하향식)
  • 메모이제이션(memoiztion)을 사용하여 다이나믹 프로그래밍을 구현하는 방식
  • 메모이제이션(memoiztion)
    • 한번 구한 계산 결과를 메모리 공간에 메모해두고, 같은 식을 다시 호출하면 메모한 결과 그대로 가져오는 기법
  • 탑다운 방식은 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 하향식이라고도 불린다.
  • 탑다운방식은 재귀함수를 이용하여 구현할 수 있다.
• Bottom-Up (상향식)
  • 타블레이션(tabulation)을 사용하여 다이나믹 프로그래밍을 구현하는 방식
  • 타블레이션(tabulation)
    • 하위 문제부터 천천히 해결하면서 더 큰 문제를 해결하는 기법
  • 하위 문제부터 시작해서 더 큰 문제를 해결해 나가기 때문에 상향식이라고도 한다.
  • 바텀업방식은 반복문을 이용하여 구현할 수 있다.