동적 계획법 (Dynamic Programming)
- 하나의 문제는 한번만 풀게 하는 알고리즘
- 메모리 공간을 약간 더 써서 연산 속도를 비약적으로 증가 시킬 수 있음
- 메모이제이션
- DP를 구현하는 방법 중 하나
- 메모리(배열)에 한 번 구한 결과를 메모해두고 같은 식을 호출하면 그대로 가져옴 (캐싱) - 분할 정복과 다른점 : DP는 분할한 문제들이 서로 영향을 미침
DP 구현 방법
- 탑다운(하향식) 방식 : 재귀를 이용해 DP 푸는 방법 (큰 문제 해결 위해 작은 문제 호출)
- 보텀업(상향식) 방식 : 반복문 이용해 DP 푸는 방법 (작은 문제부터 답을 도출함)
1. 점화식 찾기
2. dp 값이 정해져 있다면 넣고 시작하기, dp 초깃값은 큰 값 혹은 작은 값 넣기
3. 모든 dp의 값을 (점화식으로 구한 값과 현재 값 등과 비교하면서) 구하기
DP 사용 가능한 조건
- 큰 문제를 작은 문제로 나눌 수 있음
- 작은 문제에서 구한 정답이 큰 문제에서도 동일함 (정답이 바뀌지 않음)
DP 사용하는 경우
- 특정 문제를 완전 탐색 알고리즘으로 풀면 시간이 오래 걸릴 때 DP 적용 가능 여부를 확인
- 작은 문제들이 반복되는지 (답이 바뀌지 X) 확인
- dp[0], dp[1], dp[2], ... 앞의 dp들을 계산해 보면서 규칙(점화식) 찾기
- 모든 dp를 계산해야 함
- dp 배열이 1차원인지 2차원인지 잘 생각해서 문제 풀기
- dp의 점화식을 잘 짜야 함!!
