크루스칼 알고리즘크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 모두 연결하기 위해 사용하는 알고리즘이다. 또 다른 말로는 최소 신장 트리를 구하는 알고리즘이다.신장 트리란?그래프 내의 모든 정점을 포함하는 트리로써, 최소의 간선으로 모든 정점이 연결되어 있는 순환성이 없는 부분 그래프이다. 알고리즘 원리그래프에서 간선을 하나씩 추가하며 최소 신장 트리를 만드는 알고리즘이며, 간선을 추가할 때는 그리디 알고리즘을 이용해 비용이 최소인 간선을 선택한다. 연결된 정점들의 부모를 기록하며 최소 간선을 선택하며 동작한다. 동작 과정간선의 비용을 기준으로 오름차순 정렬을 해준다.낮은 비용의 간선순으로 순회하며 최소 신장 트리를 만든다.이때 주의할 점은 트리에 순환성이 생기지 않도록 간선을 생성하..
크루스칼 알고리즘
문제https://school.programmers.co.kr/learn/courses/30/lessons/42861# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해당 문제는 크루스칼 알고리즘을 이용해 최단 신장 트리를 구하며 풀이하는 문제이다.크루스칼 알고리즘을 이 문제를 통해 처음 알게되었는데, BFS 그래프 탐색인데 cost를 오름차순으로 정렬해 부모를 비교해 처리하는 알고리즘이라 생각한다. 코드const find = (parent, x) => { if (parent[x] === x) { return x; } return parent[x]..
