DP (Dynamic Programming)

동적 프로그래밍 (Dynamic Programming)

: 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

 

목적

• 수행 시간을 단축하고자 만든 알고리즘
• 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘
• 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도 개선
  • 메모리 사용: 배열 또는 자료구조 생성
  • 중복 연산 줄임 : 한 번 연산한 결과를 배열에 저장

---

푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

---

구현 방법

1. Memoization

• 중복되는 계산은 한 번만 계산 후 메모
• 하향식 접근 (Top-down), 재귀 기반 코드
• 한 번 계산 후 저장해놓고, 저장해둔 결과를 꺼내서 사용하며 구현

2. Tabulation

• 중복된는 것부터 푸는 방법
• 상향식 접근 (Bottom-up), 반복문 기반 코드
• 처음부터 테이블을 채워나간다는 식으로 계산하여 구현