DP

DP(Dynamic Programming)는 동적계획법이라고도 불리며

중복되는 부분문제를 저장하는 기법입니다.

문제의 답을 구하는 방법이 점화식을 이용하여 이전의 값들이 반복적으로 쓰이는 문제일 경우

기저사례, 점화식을 기반으로 반복적으로 쓰이는 값들을 저장하면서 코드를 작성합니다.

푸는 방법은 크게 재귀적 동적 계획법, 반복적 동적 계획법이 있으며

재귀적 동적 계획법은 메모이제이션 기법을 사용하여 점화식을 그대로 코드로 옮기기에 직관적이다는 장점,

반복적 동적 계획법은 슬라이딩 윈도우라는 기법을 이용하여 공간복잡도를 줄일 수 있다는 장점이 있습니다.

DP를 응용한 문제 중 어떠한 방법을 거쳐서 이러한 최적화 답을 구하였는지,

조건에 맞는 k번째 답을 계산하고 싶을 경우에도 작성했던 DP의 함수를 조금만 변형하여 구할 수 있습니다.

DP를 응용한 문제 또는 다른 기법과 합쳐져서 나오는 문제들이 많으므로 많이 연습해야할 기법입니다.

기본 문제

11726번: 2xn 타일링

9465번: 스티커

11062번: 카드게임

2213번: 트리의 독립 집합

2248번: 이진수 찾기