codinging

Union Find 유니온 파인드란 그래프의 관점에서 두 노드가 같은 그래프에 속하는지 빠르게 판별하는 알고리즘이다. 집합에서의 관점으로는 두 요소가 같은 집합에 속하는지 판별한다. union find 알고리즘은 두 노드가 속하는 집합을 합치는 union 과 두 노드가 같은 집합인지 확인하는 find 연산이 있다. 설명 6개의 노드로 union find 의 예시를 들어보겠다. 부모를 알 수 있는 배열을 만드는데, 각 노드는 아직 아무 연결도 되어있지 않으므로 아직 자기자신이 부모이다. 1,2를 한 집합으로 4,5,6을 한 집합으로 묶고자 한다. 먼저 위의 예시는 잘못된 예시이다. 만약, 이런식으로 부모 노드를 연결한다면 문제가 생길 것 이다. 모든 노드를 연결 한다고 가정했을때 위와 같은 방식으로 부모노..

우선순위 큐 우선순위 속성을 가지는 큐 우선순위 큐는 배열, 연결 리스트, 힙으로 구현 할 수 있다. 힙 구현 방식이 시간 복잡도가 가장 낮기 때문에 힙으로 구현한다.(O(logN)) 힙 힙 순서 속성을 가지는 완전 이진 트리(자유 저장소 힙이 아님) 힙의 삽입 연산 🐬 1 : 힙의 최고 깊이 가장 우측에 새 노드 추가.(완전 이진 트리 유지) 🐬 2 : 삽입한 노드를 부모 노드와 비교한다. 삽입한 노드가 부모 노드보다 크면 맞는 위치니 연산 종료. 🐬 3 : 삽입한 노드가 부모 노드보다 작으면 부모 노드와 삽입한 노드의 위치를 교환. 교환 후 2번 - 3번 반복 예시 다음 힙에 값이 7인 노드를 삽입하는 예시다. 값이 7인 노드를 힙의 마지막에 추가하고 부모 노드와 비교한다. 7은 31보다 작으므로 이..