dp문제 해결법

1. dp란 dp, dynamic programming의 줄임말이다. dp는 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 또한 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이라고 흔히 말한다. dp의 핵심은 앞서 말한 수행 시간 효율성의 비약적 향상인데 이는 '메모이제이션'이라는 기법을 이용해 이미 계산된 결과(작은 문제)를 별도의 메모리에 저장해 다시 계산하지 않고 필요한 경우 사용하는 방식이다. 이 기법을 사용하면 시간복잡도가 훨씬 줄어들기에 수행 시간 효율성이 비약적으로 향상한다. 2. dp 문제 유형 dp문제의 조건은 두가지이다. 1. 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제..