DP란?

---

DP란 Dynamic Programming의 약자로 한글론 ‘동적 계획법’이라고 한다. 이 이름은 대대로 엄청나게 까여왔고 쉽게 이야기하려는 분들이 가끔 ‘기억하며 풀기’라고 부르기도 한다.

‘기억하며 풀기’라는 이름에서도 알 수 있듯이 기본적인 개념은 ‘부분 문제의 답을 재활용하여 푼다.’라고 볼 수 있다.

DP로 사고하기

---

DP가 말이 ‘부분 문제의 답을 재활용하여 푼다.’라고 하지. 실제로 구현하려면 꽤 복잡하다.

나같은 경우는 순차적으로 생각하는데 이런식으로 한다.

• 완전 탐색 알고리즘을 설계한다.

  모든 답을 헤아려보는 알고리즘을 만들어본다.

• 메모이제이션

  함수의 반환값을 저장해 둘 캐시를 만들어 놓는다.

• 최적 해를 구하기 위해 최적화한다.

  DP가 쓰이는 경우는 대부분 최댓값, 최솟값에 대한 문제이다. 부분문제의 최적값을 메모이제이션하여 지니고 있는다.

예고

---

이게 직접 어떻게 쓰이는지 다음 포스트에서 알아보자.