DP 썸네일형 리스트형 1102번: 발전소 - Baekjoon Online Judge 외판원 문제(TSP: Traveling Salesperson Problem)로 대표되는 NP-난해에 해당하는 문제이다. 외판원 문제는 여러 도시가 주어졌을때 외판원이 도시별로 이동하는데 드는 비용이 각각 다른 경우 모든 도시를 다 돌고오는데 드는 비용을 어떻게 최소로 만들 것인지를 물어보는 문제이다. 외판원 문제 - 위키백과, 우리 모두의 백과사전https://ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C 발전소 문제도 이와 유사하다. 여러 발전소가 주어지고 발전소가 켜져있는 경우 그 발전소를 이용하여 다른 발전소를 켤 수 있고 그때의 비용은 각각 다르게 주어진다. 이때 최소한 켜져야하는 발전소의 숫자가 주어졌을 때 그 발전소 .. 7. 동적계획법(DP: Dynamic Programming)의 기초 동적계획법은 어떤 문제에서 최적해를 구해야할 때, 문제를 더이상 쪼갤 수 없는 단위로 쪼개서 제일 작은 부분부터 최적해를 누적해 나가는 방식으로 문제를 푸는 알고리즘을 의미합니다. 동적계획법이 가능한 것은 문제를 동일 형식의 연산이 반복될 수 있는 더 작은 문제로 쪼갤 수 있고, 작은 문제의 최적해를 이용해서 그보다 조금 더 큰 문제의 최적해를 도출할 수 있다는 것이 보장되기 때문입니다. 이러한 동적계획법의 풀이 방식에 근거하여 동적계획법 풀이는 크게 두가지가 핵심적으로 작동한다고 할 수 있는데 한 가지는 초기조건, 다른 한 가지는 점화식입니다. 초기조건은 말그대로 문제를 가장 작은 단위로 쪼개었을 때 연산없이 확정되어있는 최적해를 의미합니다. 동적계획법은 동일 연산을 가장 작은 크기의 문제부터 반복 적.. 이전 1 다음