다이나믹 프로그래밍이란?

• 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법

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

• 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식**(Top-down & Bottom-up)** 으로 구성

• 동적 계획법이라고도 부름

• 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미일까?

  → 자료구조에서 동적 할당(Dynamic Allocation)은 **'프로그램이 실행되는 도중에 필요한 메모리를 할당하는 기법'**을 의미

  → 반면 다이나믹 프로그래밍에서의 다이나믹은 별다른 의미없이 사용된 단어임

조건

• 문제가 다음의 조건을 만족할 때 다이나믹 프로그래밍 기법을 사용할 수 있다.

1. 최적 부분 구조(Optimal Substructure)

   → 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음

2. 중복되는 부분 문제 (Overlapping Subproblem)

   → 동일한 작은 문제를 반복적으로 해결해야 함

DP 기법 - TopDown, BottomUp

• 탑다운: 재귀 이용. 즉 큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출하여 작은 문제를 해결 했을 때 큰 문제까지 해결 할 수 있도록 코드 작성. 이 과정에서 한번 산출된 결과값을 저장하기 위해 → 메모이제이션 이용
• 보텀업: 아래부터 작은 문제들을 하나씩 해결해서 먼저 계산한 문제들을 활용해 다음 문제까지 차례대로 해결하는 방법 → 반복문 이용
• DP의 전형적인 형태는 BottomUp 방식
  • 결과 저장용 리스트(배열)는 DP 테이블이라고 부름.