[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

이론

 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알고리즘은 복잡하고 여러개의 연산이 있는데.. 작은 단위를 연산을 한다음 반복되거나 중복 되는 연산은 최소화 해서 풀어 나가는 알고리즘이다. 동적계획법은 시간 복잡도상에서 최적으로 나타낼수있는 강력한 알고리즘이지만 완벽한 알고리즘이라고 할수는 없다. dp로 해결하는 이유는 메모리 절약과 시간복잡도의 최적화로 되어 있지만 문제 푸는데는 어느정도 한계가 있고 이론보다는 접근 방법이나 아이디어가 더 많이 요구되기도 한다. 자세한 설명은 아래 사이트에서 찾아 보면된다.

https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 위키백과, 우리 모두의 백과사전