Dynamic Programming - 알고리즘


DP란?


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

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

DP로 사고하기


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

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

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

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

  • 메모이제이션

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

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

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

예고


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




© 2017. by isme2n

Powered by aiden