Algorithm/이론2 [알고리즘 이론] 최소 신장 트리(MST) - 크루스칼(Kruskal), 프림(Prim) 1. 최소 신장 트리(Minimum Spanning Tree) → 그리디(Greedy) 🌲 신장 트리 - n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 🎄 최소 신장 트리 - 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 📍 그래프에서 최소 비용 문제 풀 때 사용 - 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 - 두 정점 사이의 최소 비용의 경로 찾기 2. 크루스칼(Kruskal) - 간선 중심[간선 리스트 사용] - 간선을 하나씩 선택해서 MST를 찾는 알고리즘 (1) 모든 간선을 가중치에 따라 오름차순으로 정렬 (2) 가중치가 가장 낮은 간선부터 선택, 트리 증가(if 사이클이 존재, 해당 간선 사용.. 2022. 2. 23. [알고리즘 이론] 서로소 집합(Disjoint Set) 1. 정의 - 서로 중복 포함된 원소가 없는 집합이다. - 즉, 교집합이 없다. - 하나의 특정 멤버(대표자)를 통해 집합을 구분한다. 2. 표현 방법 📕 연결리스트 - 같은 집합의 원소를 하나의 연결리스트로 관리 - 맨 앞의 원소를 집합의 대표 원소로 결정 - 대표자를 찾기 위한 검색을할 때 시간이 오래걸리기 때문에 각 노드에 대표자 노드를 가리키는 링크를 만들어준다. 📗 트리 - 같은 집합 원소를 하나의 트리로 관리 - 루트 노드를 집합의 대표 원소로 결정 3. 집합 연산 - MakeSet() : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산 - FindSet(x) : x를 포함하는 집합의 대표자를 찾는 연산 - Union(x, y) : x와 y를 포함하는 두 집합을 합치는 연산(합집합) 🪄.. 2022. 2. 23. 이전 1 다음
