# 크루스칼

8개의 포스트
post-thumbnail

이것이 코딩 테스트다 :: Part2 :: Chapter 10 :: 그래프 기본 이론

Chapter 10 Section1:: 서로소 집합(disjoint sets) 개념 서로소 집합은 중복되는 원소나 교집합이 없게끔 자료를 저장하는 자료구조를 의미한다. 그래프와 연관되는 개념이지만 서로소 집합은 트리 개념(Root-Parent-Child)을 따르는 것이

2020년 9월 28일
·
0개의 댓글

그래프 알고리즘

최단경로 [다익스트라], 최소신장 트리[크루스칼, 프림] + union/find 정리

2020년 9월 4일
·
0개의 댓글
post-thumbnail

[알고리즘] 최소 신장 트리

1) 최소 신장트리의 이해 신장트리란? Spanning Tree, 또는 신장 트리 라고 불리움 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트

2020년 6월 23일
·
0개의 댓글

Algorithm(Kruskal)

Kruskal 알고리즘

2020년 4월 29일
·
0개의 댓글

[프로그래머스] 섬 연결하기 (Java)

프로그래머스 섬 연결하기모든 간선의 비용이 주어지고 가장 적은 비용으로 모든 정점을 연결하는 문제는 MST의 개념 그 자체를 나타내는 문제다. 이 문제는 크루스칼 알고리즘을 이용하여 풀었다.주어진 모든 간선을 비용을 기준으로 오름차순 정렬한다.하나씩 간선을 꺼내어 싸이

2020년 4월 26일
·
0개의 댓글
post-thumbnail

최소 신장 트리 (MST, 크루스칼, 프림 알고리즘)

원래의 그래프의 모든 노드가 연결 되어있으면서 트리의 속성을 만족하는 그래프 조건본래의 그래프의 모든 노드를 포함모든 노드가 서로 연결 되어있다트리의 속성을 만족 (사이클이 존재하지 않는다)최소 비용 신장 트리를 찾는 알고리즘 가장 적은 비용으로 모든 노드를 연결하기

2020년 4월 18일
·
0개의 댓글

그래프 최소 스패닝 트리

크루스칼 알고리즘 크루스칼 알고리즘이란 > 크루스칼 알고리즘과 프림 알고리즘은 최소 스패닝 트리를 만들기 위해 자주 쓰이는 알고리즘이다. 크루스칼 알고리즘의 원리는 매우 간단하다. 그래프의 간선들을 가중치 순으로 정렬해 가장 작은 가중치부터 그리디 알고리즘과 같이 선택해 트리에 포함시키는 것이다. 이 때 사이클이 생기면 안되므로 만약 간선이 추가됨으로서 연...

2019년 7월 25일
·
0개의 댓글

programmers 섬연결하기

문제 한줄요약: 1) 크루스칼 알고리즘으로, 2) 최소 스패닝 트리를 만든다. 최소 스패닝 트리 정점이 n개인 그래프의 간선중 일부인 n-1개의 간선을 선택해서 모든 정점을 연결한 트리중 가중치의 합이 최소인 트리 크루스칼 알고리즘 최소 스패닝 트리를 찾는 알고리즘

2019년 1월 26일
·
1개의 댓글