Algorithm
Dynamic Programming 문제를 위한 다섯 가지 단계
이진2
2021. 8. 7. 10:12
DP를 사용하는 알고리즘들은 처음의 문제를 더 작은 문제로 분할하고, subproblem들로부터 원래 문제의 답을 계산해 나가는, 분할정복과 비슷한 재귀적 문제 해결 방식이다.
DP가 분할정복과 구분되는 점은 어떤 부분 문제가 두 번 이상 사용될 시 이를 여러 번 구하지 않고 한 번만 구한 뒤 계산 결과를 재활용 할 수 있다는 특징이다.
이렇게 한 번 계산한 값을 저장해 두었다 재활용하는 최적화 기법을 memoization(메모이제이션)이라 한다 ❗
1. 문제 정의
조건과 구하고자 하는 바를 정확하게 정의
2. Recursion 정의
정의된 문제에 대한 부분 문제를 정의한 뒤 부분 문제를 이용한 점화식을 세운다
3. DP 적용 - 메모이제이션을 적용하여 점화식 계산
- 중간 계산 값을 저장할 data structure(보통 N차 array)
- 부분 문제 간의 의존성 확인
- 의존성에 기반하여 부분 문제들 간의 답을 구해야 하는 순서 정하기
4 & 5. Time Complexity 분석 및 Pseudo Code 작성
brute force방식과 비교했을 때 시간복잡도가 얼마나 향상되었는지, 설계한 대로 동작하는지 검증한 뒤 코드 작성
