Dynamic Programming 문제를 위한 다섯 가지 단계

DP를 사용하는 알고리즘들은 처음의 문제를 더 작은 문제로 분할하고, subproblem들로부터 원래 문제의 답을 계산해 나가는, 분할정복과 비슷한 재귀적 문제 해결 방식이다.

DP가 분할정복과 구분되는 점은 어떤 부분 문제가 두 번 이상 사용될 시 이를 여러 번 구하지 않고 한 번만 구한 뒤 계산 결과를 재활용 할 수 있다는 특징이다.

이렇게 한 번 계산한 값을 저장해 두었다 재활용하는 최적화 기법을 memoization(메모이제이션)이라 한다 ❗

 

1. 문제 정의

조건과 구하고자 하는 바를 정확하게 정의

 

2. Recursion 정의

정의된 문제에 대한 부분 문제를 정의한 뒤 부분 문제를 이용한 점화식을 세운다

 

3. DP 적용 - 메모이제이션을 적용하여 점화식 계산

- 중간 계산 값을 저장할 data structure(보통 N차 array)

- 부분 문제 간의 의존성 확인 

- 의존성에 기반하여 부분 문제들 간의 답을 구해야 하는 순서 정하기

 

4 & 5. Time Complexity 분석 및 Pseudo Code 작성

brute force방식과 비교했을 때 시간복잡도가 얼마나 향상되었는지, 설계한 대로 동작하는지 검증한 뒤 코드 작성

 

https://paulvanderlaken.files.wordpress.com/2019/09/travelling_salesman_problem1.png?w=640