Problem Solving/Algorithm
-
[Algorithm] 네트워크 플로우 (Network Flow)Problem Solving/Algorithm 2020. 3. 9. 00:59
네트워크 플로우 (Network Flow) 란? - 각 노드의 용량이 정해진 상태에서, 시작점에서 끝점까지 흐르는 최대 유량을 구하는 알고리즘 - 네트워크 데이터 전송, 교통 체증, 물류 시스템 등에 활용 [용어] - S : 시작점 (Source) - T : 도착점 (Sink) - c(a, b) : a에서 b로 흐를 수 있는 최대 양 (Capacity) - f(a, b) : a에서 b로 흐른 실제 양 (Flow) [제약 조건] - 용량 제한 속성 : f(u, v)
-
[Algorithm] 최소 신장 트리 (MST, Minimum Spanning Tree)Problem Solving/Algorithm 2020. 3. 8. 19:39
신장 트리 (Spanning Tree) 란? - 그래프 내의 모든 정점을 포함하는 트리 - 사이클이 형성되지 않도록 모든 정점이 연결된 트리 - 최소 연결 부분 그래프로 N개의 정점, N-1개의 간선을 가진다. [예시] 해당 그래프에서 다음과 같은 신장 트리를 구할 수 있다. 최소 신장 트리 (Minimum Spanning Tree) 란? - 주어진 그래프에서 최소한의 비용으로 만든 트리 - 간선 가중치의 합이 최소인 스패닝 트리 - 통신망, 도로망, 유통망 구축 비용 등에 활용 MST 구현 방법 - 크루스칼 알고리즘 (Kruskal's Algorithm) - 프림 알고리즘 (Prim's Algorithm) # 크루스칼 알고리즘 (Kruskal's Algorithm) - 탐욕적 방법을 이용하여 최적의 해..