1. Union-Find
Union-Find(유니온-파인드) 유니온 파인드 알고리즘은 서로소 집합을 찾는 알고리즘이다. 주로 아래와 같은 상황에서 사용할 수 있다. 여러 가지 데이터가 존재할 때 이 데이터들이 몇 개의 집합으로 묶여 있는지 파악. 무작위로 두 개의 데이터를 뽑았을 때, 두 데이터가 같은 집합의 원소인지 / 서로 다른 집합인지 파악. 위 두 경우만 봐도 서로소 집합을 찾을 때, 사용한다는 말이 와닿는다. 사실, 구체적으로는 그래프 알고리즘이다. 어떤 원소가 어떤 같은 그래프에 속하는지, 또는 서로 다른 그래프인지를 구별하는 방법인데, 아래 그림과 같다. 위 그래프를 보시면, 두 개의 그래프가 있습니다. {1,2,3,6,7}과 {4,5}로 두 그래프로 나뉘어 있다. 만약 이러한 그래프에서 "3과 4가 같은 그래프인가..
2023. 2. 21.
