![]()
0. Intro- 7-1에서 우리는 Quicksort를 직접 구현해보았다.- 이번 챕터에선 Quicksort의 시간복잡도를 한번 구해보고자 한다.- 엄밀하게 증명을 통해 구하기 보단, 직관적으로 이해하기 쉽게 알아보고자 한다. 1. Best cases- 최선의 경우 분할할 때 정확히 절반을 계속 나누는 것을 의미한다.- 깊이는 O(logn)이고, 각 순환 호출에서의 비교 연산은 O(n)이다.- 따라서 최선의 상황의 시간복잡도는 O(nlogn)이 된다. 2. Worst Cases- 최악의 경우는 정렬하고자 하는 배열이 오름차순으로 정렬되어 있거나, - 내림차순으로 정렬되어 있는 경우이다.- 깊이는 O(n)이고, 각 순환 호출에서의 비교 연산은 O(n)이므로 - 따라서 최악의 상황의 시간복잡도는 O(n^2)..
![]()
0. Intro- 이번 7 챕터에서는 quicksort, 퀵정렬에 대해서 알아보고자 한다. 1. Quicksort(퀵정렬)- quicksort(퀵정렬)은 2-3에서 배웠던 mergesort(병합정렬)과 비슷하다.- divide-and-conquer(분할정복)알고리즘을 이용한다.- 평균적으로 매우 빠른 수행 속도를 보여주기 때문에 quicksort 라고 불린다. 2. Quicksort의 알고리즘 - QuickSort의 핵심은 분할(divide)하는 과정이다. - QuickSort는 배열을 작은 부분으로 쪼개서 정렬하는 방식으로 작동하며, 다음과 같은 과정을 거친다. i) Pivot 선택- 배열에서 임의의 기준이 되는 Pivot 요소를 선택한다.- Pivot을 선택하는 방식은 크게 4가지가 존재한다. a) ..
1. Priority Queue(우선순위 큐)?- 우선 Priority Queue를 설명하기 전에, Queue에 대해서 설명하고자 한다.- Queue는 FIFO(FIrst In First Out) 즉 선입선출, 먼저 집어 넣은 데이터가 먼저 나오는 자료구조이다.- 하지만 Priority Queue는 들어간 순서에 상관없이, 우선순위가 높은 데이터부터 먼저 나오는 것을 의미한다.2. 우선순위 큐의 메소드- 우선순위 큐의 메소드는 크게 3가지가 존재한다. i) insert() : queue에 데이터를 삽입한다.ii) delete() : queue에서 최대 우선순위 데이터를 삭제하고 그 값을 반환한다.iii) peek() : queue에서 최대 우선순위 데이터를 반환한다. 2.1. Qriority Queue ..
![]()
0. Intro- 우리는 6-2, 6-3 에서 max_heapify()와 build_max_heap()을 구현해보았다.- 두 함수를 이용하여 배열을 정렬하는 알고리즘을 한번 구현해보자(Heapsort) 1. Heapsort?- 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법을 의미함- Heapsort의 알고리즘을 나타내면 다음과 같다. i) 정렬해야할 n개의 데이터들을 Max-Heap을 만든다.ii) root-node(최댓값을 가장 마지막 node와 바꾼다.iii) 그 후 heap에서 pop()을 한 후 queue에 enqueue한다.iv) 그 후 max_heapify()를 root_node에서 실행한다.v) ii)~iv)까지를 계속 반복한다. (heap이 empty가 될 때까지) - heaps..
