매뎡 창고

저번 글에서 다뤘던 Prim's Algorithm이 골라진 정점들에서 연결된 간선들중 가장 최소 가중치 값을 가지는 간선을 찾으면서 진행하는 알고리즘이였다면 이번 시간에 배우는 Kruskal's Algorithm은 각 간선을 가중치 기준으로 오름차순 정렬 한 뒤 간선의 두 정점이 서로 다른 집합일 경우 합치고, 같은 집합에 있다면 사이클이 발생하므로 합치지 않는다.이 경우 (v1,v2) 집합과 (v3,v5)집합이 (v1,v3)을 통해 합쳐지고 이 합쳐진 (v1,v2,v3,v5) 집합이 (v3,v4)를 통해 합쳐지며 minimum spanning tree를 이룬다.이 krusukal's alogirhtm의 optimality를 증명 하는 방법은 prim algorithm과 유사한 방법으로 진행한다. 1번 ..

DefinitionsSpanning Tree : 연결된 무방향 그래프 G에 대해,모든 정점을 포함하면서 사이클이 없고,연결된 부분 그래프 (subgraph) 를 말함.즉, G의 모든 정점을 포함하는 트리. 이때, 노드가 n개일경우 간선은 n-1개.Minimun Spanning Tree: 최소 가중치를 가지는 G의 Spanning TreeMST사용 예시로는 Prim's Algorithm과 Kruskal's Algorithm이 있다. Prim's Algorithm특정 정점 집합 Y에 가장 가까운 정점을 찾는 과정에서 사용 배열을 사용하여 구현 W[i][j]: 정점 i와 j 사이의 가중치 (무방향이므로 대칭)nearest[i]: 정점 Vi에 대해, 현재까지 집합 Y에 속한 정점 중 가장 가까운 정점의 인덱스..

[Greedy Algorithm] 문제 해결 과정에서 매 순간 가장 좋아 보이는 선택을 하는 방식이다.각 단계에서의 선택은 국소적으로 최적 (locally optimal) 이지만, 전체적으로도 최적인지는 보장되지 않음.한 번 선택한 것은 되돌리지 않으며, 항상 최종 해답에 포함된다.일부 문제에서는 Greedy 방식이 전역 최적해 (globally optimal solution) 를 보장하기도 하지만, 항상 그런 것은 아니다.ex) 거스름돈 문제[General Greedy Approach]1. 초기 상태빈 집합(또는 빈 상태)에서 시작2. 반복 과정문제를 해결할 때까지 다음의 세 가지 단계 반복:1. Selection Procedure (선택 절차)탐욕 기준(greedy criterion)을 바탕으로, 현..