한줄 후기 : ㅂㅇㅎ 교수님 수업 같다
신촌 알고리즙 중급 연습 문제 였는데 확률적 알고리즘 파트에서 Quick Select를 알려주셔서 그거로 풀었다.
사실 풀고 찾아보니 대부분은 그냥 c++ sort 라이브러리로도 잘 풀린다고 한다.
아 그리고 c++에 아예 Quick Select를 구현해 놓은 라이브러리도 있다는데 그걸 쓰지는 않았다.
Quick Select는 Quick Sort를 구현하면서 빠르게 n번째 원소를 찾는 기법이라고 한다.
실제 Sort는 대부분 O(nlogn)의 시간 복잡도를 갖고, 심지어 Quick Sort의 경우 Worst Case 에서 O(n^2)의 시간 복잡도를 갖는다.
방법은 간단하다.
4 | 1 | 2 | 3 | 5 |
예제이다.
그냥 Quick Sort를 일단 하던대로 시켜본다.
Pivot을 고르자.
미리 말하자면, 나는 처음에 Quick Sort 익숙한대로 맨 마지막 원소를 Pivot으로 골랐다가 TLE 를 받았다.
최악의 경우로 가는거다..
질문 검색의 한 유저분의 FAQ를 보니 이 문제는 그냥 Quick Selection 쓰지말고 라이브러리로 풀라는.. 근데 아무튼 쓰려면 Pivot을 매우 잘 골라줘야 한다고 하셨다.
그래서 두번 째 시도에서는 중간에 있는 값을 pivot으로 잡아보았다. 사실 이 방법은 RTE가 나서.. 강사님이 pivot 뽑으신 방식을 참조해 균등한 확률로 수를 뽑아내는 uniform_int_distribution 을 사용해 start ~ end 까지 중 하나를 뽑아냈다.
pivot을 뽑아내면 Quick Sort를 해준다.
예를 들어 예제에서 pivot index가 0이 되었다고 해보자. 그러면 arr[0] => 4가 pivot이 된다.
그럼 4를 맨 뒤 원소와 swap 시키자. 그리고 열심히 Quick Sort를 돌려보면
5 | 1 | 2 | 3 | 4 pivot |
3 | 1 | 2 | 5 | 4 pivot |
3 | 1 | 2 | 4 pivot | 5 |
이 된다.
그럼 K가 2기 때문에 pivot보다 왼쪽에 있는 수가 2개보다 많으면 왼쪽만 보면된다.
2개 보다 적다면 오른쪽을 봐야한다.
pivot index가 랑 같다면 그냥 pivot이 정답이 된다.
3 | 1 | 2 |
이 세 원소를 재귀적으로 돌려주면 결과적으로 우리가 필요한 K번째 수를 찾을 수 있다.
//AC
//11004 K번째 수 (Quick Select)
#include <iostream>
#include <random>
#include <time.h>
#define SIZE 5000001
using namespace std;
default_random_engine generator;
int arr[SIZE];
int N, K;
void swap(int a, int b){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
void quickSelect(int start, int end){
if(start >= end) return;
uniform_int_distribution<int> dist1(start, end);
int pivot = dist1(generator); //random pivot
int pv;
swap(pivot, end); //pivot 마지막으로
pivot = end;
int i = start;
int j = end-1;
while(i <= j){
while(i < end && arr[i] <= arr[pivot]){
i++;
}
while(j >= start && arr[j] >= arr[pivot]){
j--;
}
if(i > j){
swap(i, pivot);
}
else{
swap(i, j);
}
}
int idx = i + 1;
if(idx > K){
quickSelect(start, i-1);
}
else if(idx == K) return;
else{
quickSelect(i+1, end);
}
return;
}
int main(){
scanf("%d %d", &N, &K);
srand(time(NULL));
for(int i=0; i<N; i++){
scanf("%d", &arr[i]);
}
quickSelect(0, N-1);
printf("%d", arr[K-1]);
return 0;
}
재귀 호출 부분
int idx = i + 1;
if(idx > K){
quickSelect(start, i-1);
}
else if(idx == K) return;
else{
quickSelect(i+1, end);
}
'DEV > PS' 카테고리의 다른 글
2021 SUAPC winter 주저리.. (0) | 2021.03.04 |
---|---|
[BOJ/2912] 백설공주와 난쟁이, c++ (0) | 2021.02.19 |
[BOJ/8201] Pilots, c++ (0) | 2021.02.15 |
PS용 비트 연산자(bit masking) 정리 (0) | 2021.02.14 |
[BOJ/1516] 게임 개발, c++ (0) | 2021.02.08 |