studlog

그래프에서 최단거리는 경우에 따라 BFS, 다익스트라, 벨만 포드, 플로이드 와샬을 사용하여 구할 수 있다. 그렇다면 최장거리는 어떻게 구할 수 있을까?사이클이 없는 무향 그래프(트리)에서 최장거리트리에서는 어떤 두 노드를 선택해도 둘 사이의 경로가 항상 하나만 존재한다. 따라서 BFS을 이용하여 구할 수 있다.사이클이 없는 유향 그래프에서 최장거리일반적인 그래프에서 최장거리를 구하는 방법은 NP-Hard로 알려져 있다. 하지만 DAG(Directed Acyclic Graph)에서는 구할 수 있다. DAG에서 최장거리를 구할 수 있는 2가지 방법을 정리해보자.동적 계획법정점 $u$ → $v$의 최장거리를 구하는 점화식을 아래와 같이 세워보자.$$ D[i] = \text{정점 } i \text{ 에서} v..

배낭 문제(Knapsack Problem)는 유명한 동적 계획법 문제 중 하나이다. 배낭 문제가 어떻게 응용되는지 정리해보자.배낭 문제란?일정한 가치와 무게를 가진 짐을 담을 수 있는 최대 무게가 정해진 배낭에 담을 때, 가치의 합이 최대가 되도록 배낭에 짐을 넣는 문제이다.배낭 문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있는데 짐을 쪼갤 수 있는 경우 그리디 알고리즘으로 해결 가능하며, 짐을 쪼갤 수 없는 경우 동적계획법으로 해결 가능하다.완전 탐색짐의 개수가 \(N\)개 일 때 가능한 부분집합의 개수는 \(2^N\) 개이다. 따라서 시간 복잡도는 \(O(2^N)\)이다. → 너무 느리다.동적 계획법$$ D[i, w] = \text{배낭의 무게 한도가 }w \text{이고 }..