1. 정의
DP (Dynamic Programming)은 메모리를 사용해서 이전 계산 값들을 기억하여 중복 연산을 줄이는 완전 탐색 최적화 기법이다.
메모리를 사용하여 이전 값들을 기억한다는 의미에서
기억하기 알고리즘 이라고도 한다.2. 풀이 방법
DP는 알고리즘이 아니라 최적화 '기법'이기 때문에 정해진 형태가 없다. 따라서 문제마다 다르게 접근해야 한다. 공통적인 틀을 뽑아보자면 다음과 같이 나눌 수 있다.
- 이전 계산 값들을 기억할 자료구조 만들기 → 메모리로 이용
- 점화식 표현
- 초기값을 정한 뒤, 점화식을 활용해 메모리 자료구조 채우기
ℹ️ 점화식이란?
현재 상태의 값을 이전 상태의 값들을 이용하여 표현하는 공식
현재 상태의 값을 이전 상태의 값들을 이용하여 표현하는 공식
3. DP를 써야하는 문제 조건
- 완전탐색, BFS, DFS 등으로 풀 수 있지만 경우의 수가 많은 문제
- 경우의 수 내에서 동일 계산 중복이 많은 문제
⬅️ 이전 글