다양한 그래프 알고리즘 - 서로소 집합
안녕하세요. 오늘은 코딩 테스트에서 사용할 수 있는 다양한 그래프 알고리즘에 대해서 소개드리려고합니다. 그래프 알고리즘에 들어가기 앞서, 먼저 기초 내용부터 다지고 들어가겠습니다. 그래프 노드와 노드 사이에 연결된 간선정보를 가지고 있는 자료구조를 의미합니다. 그래서 알고리즘 문제에서 '서로 다른 개체(혹은 객체)가 연결되어 있다'는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 합니다. 트리 더불어 그래프 자료구조 중에서 트리 자료구조는 다양한 알고리즘에서 사용되므로 꼭 기억하면 좋습니다. 다익스트라 최단 경로 알고리즘에서는 우선순위 큐가 사용되었는데, 우선순위 큐를 구현하기 위해 최소 힙이나 최대 힙을 이용할 수 있다고 했습니다. 최소 힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조..