알고리즘/Greedy algorithm1 [알고리즘] Greedy algorithm (1) - Optimal solution, Kruskal, Prim [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 : 사용하는 간선의 가중치 합을 최소화하기 .. 2022. 12. 9. 이전 1 다음