<aside> 📖 Contents

</aside>

⚫️ 다이나믹 프로그래밍 (DP, 동적 계획법)

• 다이나믹 프로그래밍의 가장 큰 특징은, 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시킨다.
• 이미 계산된 결과는 별도의 메모리 영역에 저장해두었다가 나중에 해당 결과가 필요할 때 메모리 영역에 기록되어있는 정보를 그대로 사용하도록 한다. 즉, 한번 계산해서 해결한 문제를 다시 해결하지 않도록 한다. 이것이 효율적!
• dp를 이용해서 시간복잡도를 획기적으로 줄일 수 있는 경우가 많다.
• 일반적으로 두가지 top down, bottom up방식으로 구성된다.

◾️ 메모이제이션

• 메모이제이션은 다이나믹 프로그래밍 하향식!!을 구현하는 방법 중 하나이다.
• 한 번 계산된 결과를 메모리 공간에 메모하는 기법을 의미한다.
  • 한번 구한 작은 문제에 대한 값을 메모리에 저장해두었다가, 다시 사용할 수 있도록 한다.
  • 별도의 배열에다가 값을 기록한다는 점에서, Caching (캐시)라고도 한다.

◾️ 탑다운 vs 보텀업 (하향식, 상향식)

탑다운 (메모이제이션)

• 하향식
• 구현 과정에서 재귀함수를 이용함.
• 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출하여 작은문제가 모두 해결 되었을 때 큰 문제에 대한 답을 얻을 수 있도록 코드를 작성
• 그러한 과정에서 한 번 계산한 결과값을 저장하기 위해서 메모이제이션 방식 사용

보텀업

• 상향식
• 아래쪽에서부터 작은문제를 하나씩 해결해 나가면서, 먼저 계산한 값을 사용해서 다음 문제까지 차례대로 해결하는 거이 특징이다.
• 반복문을 활용해서 구현한다.