알고리즘/써먹기 좋은 알고리즘
2020. 3. 29.
Quick Selection을 이용한 k번째 숫자 탐색: O(n)의 시간 복잡도
N개의 원소 중 k번째로 작은 수를 찾아라 라는 문제를 만났을 때 가장 많이 사용하는 방법 중 하나는 컨테이너를 sorting 후에 k번째 인덱스를 참조하는 방식을 사용한다. 하지만 이렇게 정렬을 했을 경우엔 전체 시간 복잡도가 worst case O(N^2) 혹은 O(N longN)가 되어버리므로 원소의 개수가 많을 경우엔 적합하지 않다. 따라서 Quick Selection 알고리즘을 이용해서 O(N)의 시간 복잡도를 가지는 탐색을 구현할 수 있다. 이름에서도 유추할 수 있듯이 기본 idea는 Quick Sort에서 따왔다. int quick_selection(int n, int* ArrList, int k) { if (ArrList == NULL || n = mid) { std::swap(ArrLis..