1. Randomized Quicksort- 우리는 7-2 에서 Quicksort의 최악의 상황에 대해서 알아보았다.- 최악의 상황 같은 경우 매순간마다 최대,최솟값을 고르게 되면 발생하게 되는데,- 이를 최대한 방지하기 위해서 이 값을 뽑는것 자체를 random으로 뽑게되면- 최댓,최솟값을 고르게 되는 상황이 극악으로 낮아지게 되며,- 이미 정렬된 배열에서도 효율적으로 사용가능하다. 2. Code import randomdef randomlized_quicksort(arr): if len(arr) pivot] return randomlized_quicksort(left) + middle + randomlized_quicksort(right)l = [4,2,3,1,5,9,8,6,7]print(..
자료구조
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 ..
