DP

DP (Dynamic Programming) 동적계획법

• 개념 : 큰 문제를 작은 문제로 나누어서 푸는 문제
• 작은 문제들을 계산한 값을 여러 번 사용하기 때문에 Memoization (메모이제이션)이 필요하다.

---

   Memoization?

   컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해,

   매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술

 

  → 즉, 계산된 결과를 배열에 저장한 뒤, 다음 계산에서 필요하면 저장된 값을 불러옴. 시간 복잡도가 훨씬 줄어든다.

---

• 구현 방식 : Bottom-up 방식과 Top-down 방식

1. Bottom-up 방식 : 작은 문제부터 계산해 나가는 방식, for문 이용해서 처음 값부터 다음 값을 계산해 나가는 방식
2. Top-down 방식 : 큰 문제를 풀 때 작은 문제가 아직 풀리지 않았다면 그 때 푸는 방식, 일반 재귀와 같은 방식

	Bottom-up	Top-down
장점	함수를 호출하지 않으므로, 시간과 메모리를 소량 절약할 수 있다.	점화식 그대로 호출되기에, 소스의 가독성이 좋다.
단점	소스의 가독성이 저하된다.	작성하기에 조금 더 어렵다.

    문제에 따라 자신에게 맞는 방식으로 풀면 된다.