-
정의 : DP(Dynamic Programming) 한글로 동적 계획법, 프로그래밍이다. 최적화 이론의 한 기술으로써 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 말을 조금 친절하게 하면 기억하며 풀기로 기억해주면 조금 더 좋겠다. (라임 맞춘거 맞다.)
구현 : 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 구한다.
잠시 바킹독의 실전 알고리즘 (DP)편을 인용한다.
DP를 푸는 과정은
1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기
로 이뤄져 있다. 코딩테스트에 나올 수준의 DP 문제는 일단 점화식만 찾고나면 그 뒤는 초기 값을 채워넣은 후에 반복문을 돌면서 배열을 채우면 끝이어서 구현이 굉장히 쉽다고 한다. 보통 점화식은 여러개로 나눠지는 경우가 많다. 많은 문제를 풀면서 익숙해지는게 가장 중요한 것 같다.