동적 계획법3 [프로그래머스] 매출 하락 최소화 풀이 위 그림처럼 트리 구조의 형태로 이루어진 조직도가 있다. 조직도에서 임의의 노드 \(i\)와 노드 \(i\)의 자식들로 이루어진 서브 트리를 팀이라고 하자. 위의 그림에서 A, B, C, D가 팀이다. 임의의 노드 \(i\)를 팀장, 노드 \(i\)의 자식들을 팀원이라 했을 때 모든 팀에서 최소 한 명 이상 워크숍에 참석하면서, 참석하는 직원들의 하루 평균 매출액의 합을 최소로 하는 것이다. 어떤 부모 노드가 워크숍에 참석할 때 자식 노드들이 워크숍에 참석하지 않는 것이 매출액을 최소로 만들 수 있을까? 답은 아니다. 부모 노드의 평균 매출액보다 자식 노드의 평균 매출액 클 경우 반례가 만들어진다. 아래 그림이 그 반례이다. 부모 노드의 참석 여부와 상관없이 자식 노드가 워크숍에 참석했을 경우와 참.. 2022. 9. 18. 그래프에서 최장거리 그래프에서 최단거리는 경우에 따라 BFS, 다익스트라, 벨만 포드, 플로이드 와샬을 사용하여 구할 수 있다. 그렇다면 최장거리는 어떻게 구할 수 있을까? 사이클이 없는 무향 그래프(트리)에서 최장거리 트리에서는 어떤 두 노드를 선택해도 둘 사이의 경로가 항상 하나만 존재한다. 따라서 BFS을 이용하여 구할 수 있다. 사이클이 없는 유향 그래프에서 최장거리 일반적인 그래프에서 최장거리를 구하는 방법은 NP-Hard로 알려져 있다. 하지만 DAG(Directed Acyclic Graph)에서는 구할 수 있다. DAG에서 최장거리를 구할 수 있는 2가지 방법을 정리해보자. 동적 계획법 정점 $u$ → $v$의 최장거리를 구하는 점화식을 아래와 같이 세워보자. $$ D[i] = \text{정점 } i \text.. 2022. 7. 13. 배낭 문제 배낭 문제(Knapsack Problem)는 유명한 동적 계획법 문제 중 하나이다. 배낭 문제가 어떻게 응용되는지 정리해보자. 배낭 문제란? 일정한 가치와 무게를 가진 짐을 담을 수 있는 최대 무게가 정해진 배낭에 담을 때, 가치의 합이 최대가 되도록 배낭에 짐을 넣는 문제이다. 배낭 문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있는데 짐을 쪼갤 수 있는 경우 그리디 알고리즘으로 해결 가능하며, 짐을 쪼갤 수 없는 경우 동적계획법으로 해결 가능하다. 완전 탐색 짐의 개수가 \(N\)개 일 때 가능한 부분집합의 개수는 \(2^N\) 개이다. 따라서 시간 복잡도는 \(O(2^N)\)이다. → 너무 느리다. 동적 계획법 $$ D[i, w] = \text{배낭의 무게 한도가 }w \te.. 2022. 6. 6. 이전 1 다음