devlog

문제 https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 www.acmicpc.net 해설 처음 이 문제를 접했을 때 왜 Union-Find 문제인지 깨닫고 접근하기 까지 오랜 시간이 걸렸습니다. 일반적으로 Kruska..

※ https://rh-tn.tistory.com/ 와 동시에 업로드 됩니다. 목차 1. 최소 신장 트리의 정의 2. Kruskal 알고리즘의 개념 3. Kruskal 알고리즘 구현 정의 최소 신장 트리 (Minimum Spanning Tree)에 대해 알아보기 전에 우선 신장 트리가 무엇인지 알아보겠습니다. 신장 트리(Spanning Tree)는 무방향 연결 그래프가 존재할 때, 그 그래프에서 모든 정점을 포함하도록 간선을 부분적으로 선택하여 만들 수 있는 부분 그래프 입니다. 어떤 그래프가 정점 V개와 E개의 간선을 가지고 있다고 가정하면 신장 트리의 정점과 간선의 개수는 각각 V와 V-1이 되겠습니다. 최소 신장 트리는 그 중에서도 가중치가 있는 그래프일 때를 고려합니다. 그래프의 간선마다 가중치가..