# 신장트리(Spanning Tree) 신장(spanning): 간선의 갯수를 가장 작게 노드를 전부 이어라.(= n-1개) n개 정점 n-1개의 노드 # 최소 신장트리(MST: Minimum Spanning Tree) 네트워크에 있는 모든 정점들을 가장 적은 수의 (간선 + 비용)으로 연결 최소: 비용을 가장 작게 신장: 최소한의 간선으로(= n-1개) => 즉 최소신장트리는 싸이클이 없다. # 크루스칼 알고리즘 그리디: 전체적인 해답을 찾는다는 희망으로 매 순간 최선의 선택을 하는 것. 과연 근데 그게 궁극적으로 최선인 걸까? ex) 네비지도를 보고 가다가 잠시 빠른 길로 간 게 뒤에가 다 막히는 길이여서 더 늦을 수 있음. => 따라서 매 순간 최선의 선택이 최적의 해답임을 보장할 수 없음. 그런데..
우선순위 큐 우선순위를 가진 항목들을 저장하는 큐 우리가 정한 우선순위대로 정해진 큐 원래라면 1차선 도로처럼 FIFO 순서대로 나아가는 것을 큐(Queue)다. 2차선처럼 우선순위가 높은 데이터가 먼저 나가는 것이 우선순위 큐다. 숫자의 크기를 가지고 일단 우선순위 큐를 만들어보자. 우선순위 큐(heap)은 2가지로 구분 최소 우선순위 큐 (min heap) 최대 우선순위 큐(max heap) 우선순위 큐 구현방법 3가지가 존재한다 1. 배열을 이용한 우선 순위 큐 정렬이 안된 배열 정렬이 된 배열 삽입 - O(1) 가장 뒤에 삽입 삭제 - O(n) 처음부터 끝까지 모든 요소를 check하여 삭제 삽입 - O(n) 모든 요소와 삽입할 요소의 우선순위를 비교하여 삽입위치 결정(이진탐색) 삭제 - O(1)..
MST 중 prim알고리즘은 그리디알고리즘을 만족하는 몇 안 되는 알고리즘이다. 여기서 mst = minimum spaning tree로 최소신장트리이다. 신장트리 중 가중치의 총합이 가장 최소임을 의미한다. 특징으로는 1. 간선의 가중치의 합이 최소여야 한다. 2. n개의 정점을 가지는 그래프에 대해 반드시 (n-1) 개의 간선만을 사용해야 한다. 노드 1번에서 가질 수 있는 간선의 수 : 2(N-1) 노드 2번에서 가질 수 있는 간선의 수 : 2(N-2) 노드 3번에서 가질 수 있는 간선의 수 : 2(N-3) 이를 모두 더하면 2(N-1 + N-2 + N-3 + .... + N-N) 2*(N^2 - (N(N+1)/2)) E = N(N-1) 이다. 이때 prim알고리즘은 현재 보이는 것 중 가장 좋은 ..
