[1. Greedy algorithm]
1. greedy algorithm
→ 단계마다 한 번에 하나의 입력을 고려하되, 그 단계별로 최적의 선택을 하는 것
→ 항상 최적의 결과를 도출하는 것은 아님, 다만 최적의 근사치를 도출할 수 있음
2. Minimum cost of spanning tree
→ 가중치그래프의 spanning tree에서 가중치의 합이 가장 적은 탐색방법 모색
→ cycle 비허용
→ Solution : 모든 개체들을 연결하기
→ constraint : 개체가 n개 존재한다면, 최대 n-1개의 간선을 사용하기
→ Feasible solution : 최대 n-1개의 간선을 사용해서 모든 개체들을 연결하기
→ objective function : 사용하는 간선의 가중치 합을 최소화하기
→ Optimal solution : 최대 n-1개의 간선을 사용하되 그 가중치의 합을 최소화하며 모든 개체들을 연결하기
Ex)
(1) Kruskal's algorithm
→ 간선들을 가중치에 대하여 집합 E에 오름차순으로 정렬
→ 개체가 n개일 경우 n-1개의 원소를 저장할 수 있는 집합 T 생성
→ 그래프에서 가중치가 가장 낮은 간선(u, v)를 집합 T에 입력 후 집합 E에서 제거
→ 위의 선택을 반복하되, 어느 간선을 선택했을 때 cycle이 생긴다면 그 간선은 선택X
→ 시간복잡도 : O(mlogm+n²)
→ union find 알고리즘 : Disjoint set에 대한 union & find 연산 진행
→ disjoint : 서로 교집합이 공집합인 집합
→ union : 서로 다른 두 집합에 대한 합집합 계산
→ find : 임의의 원소가 속한 집합의 label을 추출
→ forest기반 구현
→ 시간복잡도 : O(mlogm)
Ex)
(2) Prim's 알고리즘
→ 집합 U와 T를 생성한 후
→ 방문한 개체는 U에 저장하고 지나온 간선은 T에 저장한다
→ 집합 U에 저장된 개체에서 U에 저장되지 않은 개체로 향하는 간선들 중 가중치가 가장 낮은 간선을 선택하여 연결된 개체를 U에 저장한다 (heap 사용)
→ 위의 과정을 모든 개체가 U에 저장될때까지 반복한다
→ 시간복잡도 : O(mlogm)
Ex)
