kark's

각 원소가 집합을 이루게 하거나, 집합을 관리하기 위해 사용되는 자료구조 각 원소가 어떤 집합에 속하는지 빠르게 찾아내고 두개의 집합을 하나로 합치는 연산을 지원한다. 최소 신장트리 알고리즘, 사이클 감지에 유용하다. DisjointSet에 각 원소를 추가시켜둔 상황이다. 처음은 집합을 설정하지 않았으므로 집합은 총 원소개로 구성된다. 집합을 만들어보자. Union 메서드 Union(2,5) 2와 5를 하나의 집합으로 구성시킨다. 서로 각자를 대표하는 값중 어떤값이 더 작은지 확인하고, 큰값의 부모를 작은값으로 수정하는 등의 설정이 필요하다. 이로써 자신의 집합중 어떠한 값이 집합을 대표하는 값인지 바로 확인이 가능하다. Union(3,5) 3과 5의 원소를 집합으로 구성시키려한다. 이때 각 대표값들을 ..

일반적인 Queue 같은경우 FIFO(First In First Out) 구조로 먼저 들어가 있던 데이터가 가장먼저 반환되는 자료구조이다. Priority Queue는 먼저 들어가있는 순서는 상관없이 우선순위가 가장 높은것 먼저 배출되는 자료구조이다. 예시는 낮은수가 우선순위가 높다고 가정한다. 내부 원리를 이해해보자. 우선순위 큐는 이진트리 형식으로 구성되어있으며, 이 트리 구조를 활용해 빠르게 우선순위를 쉽게 확인할수 있다. Enqueue 우선순위 큐에 2, 4, 3 의 데이터 3개가 들어있고 새로운 데이터 1을 삽입하는 과정 위처럼 이진트리의 순서대로 맨 마지막 자리에 전달받은 요소를 추가시켜준다. 이후 자신의 부모 노드보다 우선순위가 높다면 자리를 교체해주며 트리의 Head까지 과정을 반복해주면 ..