동적 프로그래밍 문제 파악
-
동적 프로그래밍으로 해결하는 문제는 모든 경우의 수를 파악하여 진행하면서 지수승의 시간 복잡도를 가지는 경우가 많다.
-
모든 경우의 수를 조합하면서, 확인하는 과정을 가지는 문제는 동적 프로그래밍 접근법이 가능하다고 보면 된다.
-
다음과 같은 키워드가 들어가면, 동적 프로그래밍 접근법을 이용하여 풀 수 있는 문제이다.
"shortest", "longest", "minimized", "maximized",
"least", "most", "fewest", "greatest", "biggest", "smallest"
단계별 동적 프로그래밍 문제 해결 방법
- 전체 탐색(
Brute Force) 방법으로 우선 문제를 해결해본다. - 그 다음에 해당 풀이를 분석하여, 반복되는 작업을 정리한다, 즉 전체 탐색에서 하위 문제로 쪼개어보고 반복되는 단계가 있는지를 찾아낸다.
- 순조롭게 진행되면 역으로 동적 방식이 용이하다고 판단할 수 있다.