알고리즘

퀵 정렬은 분할 정복법을 이용한 정렬 알고리즘이다. 기준 원소 $p$(pivot)를 정하여 정렬하고자 하는 리스트를 $LT$ ($p$보다 작은 원소들), $EQ$ ($p$와 같은 원소들), $GT$ ($p$보다 큰 원소들)의 세 부분으로 분할하고, $LT$와 $GT$를 재귀를 통해 각각 정렬 후, 세 부분을 합쳐 정렬을 완료한다. def quickSort(L): if len(L)> 1: i = -1 # pivot, 보통은 마지막 원소를 사용 LT, EQ, GT = partition(L, i) quickSort(LT) quickSort(GT) L = merge(LT, EQ, GT) return L 리스트 분할 리스트의 각 원소를 차례대로 꺼내어 기준 원소 p와 비교하여 분할하기 때문에, 분할 단계는 $O(..

분할 정복법Devide and Conquer 분할 정복법은 대표적인 알고리즘 설계 기법의 일종으로, 큰 문제를 작은 문제 여러 개로 분할하여, 하나씩 해결하는 기법이다. 분할 정복의 예시로 합병 정렬과 퀵 정렬이 있다. 합병 정렬 분할 정복법을 이용한 정렬 알고리즘이다. 힙 정렬과 마찬가지로 비교에 기초한 정렬이며, $O(n\log n)$ 시간에 수행된다. 힙 정렬과는 달리 외부의 우선순위 큐를 이용하는 것이 아니라, 데이터에 순차적으로 접근하여 정렬하므로, 순차 데이터를 정렬하기에 적절하다. def mergeSort(L): if len(L) > 1: L1, L2 = L[:len(L)//2], L[len(L)//2:] # Devide mergeSort(L1) # Conquer mergeSort(L2) L..

insertItem, removeMin 함수가 $O(\log n)$의 시간복잡도를 갖는 힙으로 구현된 우선순위 큐를 사용하면, $n$개의 원소를 갖는 리스트를 $O(n\log n)$시간에 정렬할 수 있다. 이는 $O(n^2)$ 시간이 걸리는 선택정렬이나 삽입정렬에 비해 훨씬 빠른 속도이다. def heapSort(L): H = Heap() while !L.isEmpty(): k=L.removeFirst() H.insertItem(k) while !H.isEmpty(): k=H.removeMin() L.addLast(k) return L 힙 정렬의 개선 제자리 힙 정렬은 힙 정렬의 공간 복잡도를 줄일 수 있다. 상향식 힙 생성은 힙 정렬의 속도를 높일 수 있다. 제자리 힙 정렬 정렬할 리스트가 배열로 주어..

힙 힙은 내부노드에 키를 저장하며, 다음 두 가지 속성을 만족하는 이진트리이다. 힙 순서(Heap Order): 루트노드를 제외한 모든 내부노드 $v$에 대해, $\text{key}(v)\geq \text{key}(\text{parent}(v)) $ 완전 이진 트리: 힙의 높이를 $h$라 하면, $i=0, \cdots h-1$에 대해, 깊이 $i$인 노드가 $2^i$개 존재 깊이 $h-1$에서, 내부노드들은 외부노드의 왼쪽에 존재 힙의 마지막 노드는, 깊이 $h-1$의 가장 오른쪽 내부노드이다. 힙의 높이 $n$개의 키를 저장하는 힙의 높이는 $O(\log n)$이다. 깊이 $i=0, 1, 2, \cdots , h-2 $에 $2^i$개의 키, 그리고 깊이 $h-1$에 적어도 한 개의 키가 존재하므로 $n..

원소와 키가 존재하는 큐. 각 항목이 (키, 원소) 쌍으로 구성됨. 우선순위 큐의 주요 함수 void insertItem(e, k); // 키 k인 원소 e를 삽입 elem removeMin(); // k가 가장 낮은 원소 삭제, 반환 int size(); boolean isEmpty(); elem minElement(); // k가 가장 낮은 원소 반환 elem minKey(); // 가장 낮은 k 반환 우선순위 큐를 활용한 정렬 우선순위 큐를 이용하여 리스트를 정렬할 수 있다. def PQ-sort(L): P = PriorityQueue() while(! L.isEmpty()): e = L.pop() P.insertItem(e) while(! P.isEmpty()): e = P.removeMin() ..