DP

1. DP란? 동적 계획법은 간단히 말하면 전체 문제 혹은 큰 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들로 나눠서 해결하고 이것들을 활용해 전체 문제를 해결하는 방법이다. 말만 들어보면 다른 알고리즘인 분할정복과 유사하게 보인다. 다만 DP를 효율적으로 사용하기 위해서는 2가지 조건을 만족해야한다. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 한다.(중복 부분 문제) 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 한다.(최적 부분 구조) 분할정복과 DP 모두 부분 문제로 나눠서 해결한 뒤 원래 문제의 해답을 얻지만, 분할정복은 반복되는 작은 문제가 없다. 반면에 위에서 살펴본 것처럼 DP는 반복되는 작은 문제가 있을 때 사용하는 알고리즘이다. ..