서로소 (1) 썸네일형 리스트형 [문제해결기법] 8. 서로소인 집합의 표현 (Disjoint Sets) 서로소인 집합의 표현 (Disjoint Sets) 서로소인 집합 : 전체집합의 부분집합들 중, 둘을 고르면 교집합=공집합, 전체 합집합=U U의 두 원소가 같은 부분집합의 원소인지 아닌지 어떻게 알 수 있을까? 신장트리 : 그래프 G의 노드를 모두 포함하는, E에 속하는 에지로 만든 트리 최소신장트리 : 트리에 속한 가중치의 합이 가장 작은 신장 트리. 최소 신장 트리 (MST) 만들기 Prim’s algorithm : 현재 집합(노드들)과 연결된 에지 중 가중치가 최소인 것을 MST 집합에 포함시킴. 구현법에 따라 시간복잡도가 차이남 다익스트라 알고리즘 = 특정 시작노드부터 다른 노드들까지의 최단거리를 구함. 유/무향 그래프 프림 알고리즘 = 모든 노드들을 최소비용으로 연결 / 두 노드사이의 거리는 최.. 이전 1 다음