Programming/Data Structure (2) 썸네일형 리스트형 [자료구조] 우선순위 큐(Priority Queue), Heap 우선순위 큐 우선순위를 가진 항목들을 저장하는 큐 우리가 정한 우선순위대로 정해진 큐 원래라면 1차선 도로처럼 FIFO 순서대로 나아가는 것을 큐(Queue)다. 2차선처럼 우선순위가 높은 데이터가 먼저 나가는 것이 우선순위 큐다. 숫자의 크기를 가지고 일단 우선순위 큐를 만들어보자. 우선순위 큐(heap)은 2가지로 구분 최소 우선순위 큐 (min heap) 최대 우선순위 큐(max heap) 우선순위 큐 구현방법 3가지가 존재한다 1. 배열을 이용한 우선 순위 큐 정렬이 안된 배열 정렬이 된 배열 삽입 - O(1) 가장 뒤에 삽입 삭제 - O(n) 처음부터 끝까지 모든 요소를 check하여 삭제 삽입 - O(n) 모든 요소와 삽입할 요소의 우선순위를 비교하여 삽입위치 결정(이진탐색) 삭제 - O(1).. [MST] Prim & Greedy 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알고리즘은 현재 보이는 것 중 가장 좋은 .. 이전 1 다음
