유블로그

그래프에서 최소 비용 문제 모든 정점 연결 간선들 가중치 합이 최소가 되는 트리 두 정점 사이 최소 비용 경로 찾기 신장 트리 : n개 정점 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리(Minimum Spanning Tree) : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치 합이 최소인 신장 트리 : 서로소 집합 사용 간선을 하나씩 선택해서 MST 를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬(최대신장트리는 내림차순) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 - 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택(union 연산 실패 상황) n-1 개의 간선이 선택될 때까지 2를 반복 ..

서로소 집합 중복 포함된 원소가 없는 집합. 집합에 속한 하나의 특정 멤버인 '대표자'로 집합 구분 연결리스트 or 트리로 표현 서로소 집합 연산 Make-Set(x) : 유일한 멤버 x 포함하는 새로운 집합 생성 Find-Set(x) : x 포함하는 집합 찾기 Union(x, y) : x와 y 를 포함하는 두 집합을 통합하는 연산. x와 y 중 x를 대표자로 설정한다면 x는 y의 부모가 됨. 하나의 집합 = 하나의 트리 자식 노드가 부모 노드 가리킴. 루트 노드가 대표자 대표자 노드는 자기자신을 가리킴. Rank 사용 : 각 노드는 자신을 루트로 하는 subtree의 높이를 Rank로 저장 Path Compression : Find-Set 할 때 만나는 모든 노드들이 직..