성장하고 개발하는 계란의 이야기

문제  풀이고려해야할 점더보기친구의 친구의 친구도 친구로 칠 수 있다. 즉 어떤 친구 집단 트리 A가 있을 때 그 중 한 명만 친해도 그 집단 전체와 친구가 되었다고 할 수 있다. 이를 계산하기 위해 서로 연결되어 있는 친구 집단을 구해야 한다. 이 결과를 바탕으로 친구비를 최소로 하는 경우의 수를 찾아야 한다. 중복되는 친구 관계, 혹은 자기 자신과 친구인 경우를 확인해야 한다. 모두 친구를 만들 수 없는 경우 "oh no"를 출력해야 한다.  알고리즘 분류(백준 기준) 더보기자료구조그래프 이론 그래프 탐색분리 집합유니온 파인드  풀이 아이디어 더보기집합 관계를 효율적으로 판별하기 위해 유니온 파인드를 사용하였다. 두 집합을 합칠 때는 친구비의 값이 더 싼 쪽이 부모가 되도록 결합하였다. 각 집합의 최..

개념 최소 신장 트리(MST,  Minimum Spanning Tree)연결된 무방향 가중치 그래프에서 모든 정점을 포함하면서, 가중치의 합이 최소가 되는 트리  위 내용은 gpt가 설명하는 MST의 정의입니다. 두 정점 사이의 간선이 서로 다른 가중치를 가지는 그래프에 대하여 최소 신장 트리는 다음과 같은 특징을 만족합니다. 모든 정점을 포함사이클이 없음 간선의 가중치 합이 최소 아래 그래프를 예시로 들어보겠습니다.  위 그래프에서 최소 신장트리는 다음과 같습니다. 최소 신장 트리를 구하는 대표적인 알고리즘은 크루스칼과 프림 알고리즘이 있습니다. 이번 게시물에서는 그 중 크루스칼에 대해 알아보고자 합니다.  크루스칼 알고리즘(kruskal's Algorithm)간선을 가중치 순(오름차순)으로 정렬한 후..