동적 계획법( DP : Dynamic Programming ) 이란?
- 다이나믹 프로그래밍은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장( 메모이제이션 )하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 방법입니다.
메모이제이션( memoization )이란?
- 메모이제이션이란 어떤 로직에 의한 결과값이나 상태값을 자료구조에 저장하여 재사용할 수 있도록 하는 것을 말합니다.
DP 적용 조건
참조 투명성을 가져야 합니다.
- 입력을 제외한 외적 요소에 결과값이 영향을 미치지 않아야 합니다.
Overlapping Subproblem
Optimal Substructure
- 최적 부분 구조를 가지고 있어야합니다. 즉, 최적의 해가 전체적인 글로벌한 최적해가 되는 것을 말합니다.
현실적인 코딩 테스트에서 DP를 적용하기까지 생각 과정
1. 완전탐색 문제인데?
2. 경우의 수가 너무나 큰데?
3. 메모이제이션이 가능한가?
- 저장해야할 메모이제이션이 너무 클 경우 그리디로 풀어야합니다.
자료 참조 : https://blog.naver.com/jhc9639/222349317111