Coin

동적 계획법이란? 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 하위 문제의 해결책이 다른 하위 문제의 해결책과 같은 경우 유용하다. 탐욕 알고리즘과의 비교 탐욕 알고리즘은 문제가 발생하면 그 상황에서의 최적의 해를 선택하는 방식의 알고리즘을 말한다. 순간적으로 볼 때는 최적의 해를 반환하지만 전체적으로 보았을 때 그렇지만은 않은 상황이 존재한다. 예를 들어, 길을 찾는 문제가 주어졌다면 출발지부터 목적지까지 가는 중, 갈림길과 마주했을 때 그 순간 가장 짧은 길로 가는 것이다. 하지만 동적 계획법은 모든 갈림길을 살펴본 후 최적의 길을 탐색하게 된다. 동적 계획법은 모든 경우의 수를 살펴봐야 하기 때문에 시작시 조금의 시간이 걸릴..