Spanning Tree - 신장 트리 노드의 갯수가 N개일때 모든 노드가 연결되어 있고 간선의 갯수가 N-1개인 트리를 Spanning Tree라고 한다. N개의 모든 노드가 연결되어있고 최소 갯수의 간선(N-1)을 가지기 때문에 Spanning Tree는 트리내에 사이클이 존재하지 않는다. MST (Minimum Spanning Tree) - 최소 신장 트리 MST는 Spanning Tree에서 사용된 간선의 가중치 합이 가장 작은 트리를 의미한다. 모든 노드를 최소한의 간선과 최소한의 비용으로 연결하는것을 말한다. 참고자료 [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog Step by step goes a long way..
Heap Heap은 최솟값, 최댓값을 빠르게 찾기 위해 고안된 자료구조이고, 무엇인가를 차곡차곡 쌓아 놓은 더미와 비슷하다 하여 Heap이라고 부른다. Heap은 '이진 트리'이되 '완전 이진 트리이다. '이진 트리'란 각 노드가 자식 노드를 최대 두개까지 가질 수 있는 트리를 말하며 '완전 이진 트리'란 마지막 레벨을 제외하고 모든 레벨이 채워져 있는 트리를 말한다. 탐색보다는 삽입과 삭제에 최적화된 자료구조이다. Array, Linked List에서 데이터 저장의 시간 복잡도는 O(n)이지만, Heap은 O(logn)이라는 좋은 성능을 보여준다. 그 이유는 Heap에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 늘 때마다 두 배씩 증가하기 때문에, 데이터의 수가 두 배 늘 때마다 비교연산의 횟수..
Priority Queue Priority Queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. Queue와 구조가 비슷할 것 같지만 둘은 많은 차이가 있다. Queue는 연산의 결과로 FIFO 즉, 먼저 들어간 데이터가 먼저 나오지만 Priority Queue는 그렇지 않다. 앞서 설명한 것처럼 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. Priority Queue는 Array, List, Heap으로 구현할 수 있다. 하지만 Array와 List는 데이터 삽입과 삽입 위치를 찾는 과정에서 성능을 저하시킬 수 있기때문에 일반적으로 Heap을 이용해 구현한다. Priority Queue의 개념은 사실상 Heap에 대한 개념과 같기 때문에 Heap에 대한..
