개발 일지

얼만큼의 비용과 보상이 정해진 여러개의 물체가 있다고 하자. 특정 용량까지 수용 가능한 마대에 이 물체들을 마대의 최대 수용량을 넘기지 않게 넣어주되, 담겨있는 물체들의 보상의 합이 가능한 경우의 수 중 최대가 되게 하려고 한다. 이 때의 경우를 구하는 것이 본 문제의 핵심이다. 예를 들면 보석의 수 n이 4로 주어지고, 각각 다음과 같은 조건을 만족한다. profit = {1, 2, 5, 6} weight = {2, 3, 4, 5} 보석을 담을 마대의 수용량 m은 8로 주어졌을 때 어떤 보석을 챙겨야 가장 많은 보상을 챙길 수 있을까? 단순히 생각하면 각 보석을 담는 모든 경우의 수 중 한계 수용량을 넘는것을 제외하고 가장 보상의 값이 큰 조합을 찾으면 될 것이다. 하지만 이 경우 2^4 만큼의 연산을..

위 그래프에서, V1에 위치한 노드 "1"이 V5에 위치한 노드 "12"까지 도달하는데까지 최소비용으로 갈 수 있는 경로를 찾으려고 한다. 물론 다익스트라 알고리즘을 통해 해결 가능하지만, DP 적 접근을 조명하여 문제를 해결해보고자 한다. 모든 내용은 맨 하단 남겨놓은 강의를 바탕으로 한다. "다이나믹 프로그래밍" 기법이 사용되기에 합당한 상황이란, 반복적으로 최적의 선택을 골라 답을 도출해야 하는 때 이다. 위 문제 역시 각 스테이지를 이동하며 최종적으로 가장 비용이 적게들게 하는 경로를 선택해야 하므로, DP에 대한 접근이 타당하다고 할 수 있다. 하지만 이전에 푼 백준 14501번 퇴사 문제와 마찬가지로, 최적의 경로를 찾아야 하는 상황이지만 그 최적의 경로라는 것이 최종적으로 봤을 때가 기준이라..