유니온 파인드1 유니온 파인드 최근에 졸업 시험과 기업 코테를 포함하여 여러번 코테를 쳤다. 그중에서 n의 크기가 300,000으로, 아무리 봐도 최소 nlogn 안쪽으로 풀어야 할 것 같은데 완탐 풀이법밖에 생각나지 않는 문제들이 2개 있었다. 그들의 공통점은 union find로 풀어야 하는 문제였다는 것이었다. 첫번째 문제를 만났을 때 유니온 파인드를 공부했다면 다른 문제는 풀 수 있었을지도 모르는데... 역시 모르는게 생기면 공부를 바로바로 해야 한다. 유니온 파인드에 대하여 유니온 파인드의 다른 이름은 서로소 집합이다. 두 집합이 서로소 관계인지를 확인할 수 있다는 말은 각 집합이 어떤 원소를 공통으로 가지고 있는지 확인할 수 있다는 말과 같다. 그렇기 때문에 union-find라고 부른다. 기본 유형은 위 그래프의 연결 관.. 2022. 9. 16. 이전 1 다음 반응형
