후르트링의 CS 블로그

[ Heap의 정의 ] 우선순위 큐를 구현한 완전 이진트리로 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 이진트리. 높이가 작은 곳부터, 왼쪽부터 삽입하는 방식으로 작동하며 느슨한 정렬 상태를 유지합니다. 종류로는 최소힙, 최대 힙이 있습니다. 위의 그림은 최소 힙을 나타내었습니다. 최소 힙(Min Heap) : 부모 노드의 값이 자식 노드보다 작다. 최대 힙(Max Heap) : 부모 노드의 값이 자식 노드보다 크다. Heap은 이진 탐색 트리(Binary Search Tree)와 비슷한 트리이지만, 자식과 부모 사이의 대소관계가 다릅니다. Heap은 중복값을 허용, 이진 탐색 트리는 중복값을 허용하지 않습니다. Heap에서 할 수 있는 것은 이진 탐색 트리에서도 가능한데 힙을 쓰는 이유가 무엇일까요? ..

[ 신장트리(Spanning Tree) ] 주어진 방향성이 없는 그래프의 서브 그래프(Subgraph)들 중에서 모든 정점을 포함하는 트리 사이클이 존재하지 않습니다. [ MST ] 그래프의 신장 트리 중에서 간선들의 가중치 합이 최소인 신장트리를 MST(최소 비용 신장 트리,Minimum Spanning Tree)라고 합니다. 간선들의 가중치의 합이 최소 V개의 정점 그래프는 V-1개의 간선 사이클 존재 X 총 3가지의 특징을 가지고 있어야 합니다. 최소 비용 신장트리를 찾는 방법은 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 대표적입니다. 두 가지 모두 그리디 방식으로 구현합니다. 최소 비용 신장 트리는 통신 네트워크 구축, 배관 파이프 건설 등에서 사용될 수 있습니다. [ 크루스칼..