DP(동적 계획법)에 대해 설명하세요
Keyword
큰 문제, 작은 문제, 겹치는 부분 문제, 최적 부분 구조, Top-Down, Bottom-up, Memoization, Tabulation
Script
DP는 큰 문제를 작은 문제로 쪼개서 문제를 해결하는 일종의 패러다임입니다. DP를 사용하기 위해서는 2가지 조건을 만족해야 하는데,
첫째로 동일한 부분 문제들이 반복하여 나타나야하고 (겹치는 부분 문제, Overlapping Subproblems),
이 부분 문제의 최적 결과 값을 기반으로 전체 문제의 최적 결과를 낼 수 있어야 합니다. (최적 부분 구조, Optimal Substructure)
DP를 구현하는 경우 크게 Top-Down과 Bottom-up 방식으로 나눌 수 있습니다.
Top-Down은 찾고자 하는 전체 문제의 최적해를 나타내는 곳에서 출발해서 재귀를 통해 문제를 해결합니다. 이때, 상태 값을 저장해두는 Memoization 기법을 사용합니다.
반면, Bottom-up 방식은 기저 상태부터 시작하여 목표 상태까지 점화식을 통해 Table에 상태를 기록해나가면서 문제를 해결합니다. 이때 사용되는 기법을 Tabulation이라고 부릅니다.
Additional
분할정복과의 차이
먼저 분할정복과 DP의 공통점은 "주어진 문제를 작게 쪼개서 하위 문제를 해결하여, 결국 큰 문제를 해결한다"이다.
하지만 분할 정복의 경우 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰이고, 동일한 중복이 일어나는 경우에는 동적 프로그래밍을 사용한다.
with programming