DP(Dynamic Programming)

핵심요약

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법
• 간단한 구현, 복잡한 점화식
• 최적의 원리가 성립해야함.

최적의 원리
"어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다.”

 

문제 풀이 순서

1. 문제 탐색
   1. DP 배열에 어떤 값을 저장할 것이고, 인덱스는 어떤 것을 의미할지 정의를 한다.
   2. dp 벡터를 선언할 때 최소값을 찾을경우 MAX로, 최대값을 찾을경우 MIN으로 선언한다.
2. DP식(점화식) 세우기
   1. 메모이제이션된 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 어떻게 구할지를 고민한다.
3. 검증 및 구현(시간 복잡도)

 

문제 유형

1. 결과값들 더하기.
2. 결과값들 중 최대, 최소 구하기.
3. 배낭 채우기(Knapsack Problem)

 

문제 추천

https://stonejjun.tistory.com/24

좋은 DP 문제들 추천

 

아직 DP 유형에 익숙하지 않아 정리본도 많이 부족하다.

자세하게 공부하고 나서 추후에 보완할 예정이다.