Junnnho

Quick_selection 은 N개의 요소 중에서 정렬했을 때 K번째 요소의 값을 알고싶다면

K번째 요소의 값을 알 때 까지만 정확히 정렬을 구현하고 나머지 필요없는 계산은 하지않는 방법이다.

사실상 전체정렬이 다 필요하지 않은 경우라면 나머지계산은 할 필요가 없기 때문이다.

11004번은 뭔가 문제가 많이 심오하다.

여러 많은 블로그들을 보며 quick selection 을 공부하였지만 

결국 핵심은 partition 함수를 잘 작성했느냐 못했느냐 이다.

pivot 의 위치를 어떻게 조절하느냐에 따라 최악의 경우 O(N^2) 까지도 갈 수 있기 때문이다.

백준의 djm03*** 님 공지글을 읽어보면 quick sort 자체가 최악의 경우 O(N^2) 에 걸리는 부분이 많다고 하셨다.

당장 11004번은 STL의 sort를 이용해서 O(NlogN) 으로 문제가 풀리긴 한다

하지만 문제가 요구하는대로 풀려면 분명 quick selection 을 이용하는것이 맞다.

문제는 일단 STL 에 구현된 원하는 지점까지만 정렬을 하는 nth_element 를 사용해서 풀었지만

quick selection 을 공부하고자 코드는 직접 작성해보고 있다.

계속 시간초과가 나서 기존의 알고있던 quick sort 의 partition 부분은 .. 버릴려고한다 ㅠㅠ

partition 함수를 pivot이 첫번째 값일때부터 끝값까지 다 검사하는 방식을 쓰니 시간초과가 난다.

최악의 경우인 인풋값에 걸리나보다.

pivot을 중간에 두고 start 와 mid+1 을 기준으로 하는 방식인

merge 방식의 partition 을 사용해서 통과하는 분을 보았으니

merge 방식으로 partition 을 고려해볼만한 것 같다.

quick selection 의 정확한 개념을 알고 싶으신 분들은 참조해보면 좋을 것 같다.

항상 애용하는 Crocus 님 : https://www.crocus.co.kr/403

BOJ : https://www.acmicpc.net/problem/11652

처음에는 2^62 라는 수때문에 숫자타입형으로 표현이 안되는줄 알았다.

그래서 string 으로 N^2 라는 시간복잡도에 풀어냈는데

2^62라는 범위가 숫자타입형으로 표현이 되는줄 알게 되어서 다시 풀어보았다.

첫번째 if문은 숫자가 달라질 때 최대수가 더 적으면 갱신을 해주는 작업이고

두번째 if문은 숫자가 달라질 때 최대수가 현재 수와 같다면 갱신을 해줄 필요가 없는 부분이고

세번째 if문은 카운트해주는 부분이다.

마지막조건은 끝까지 탐색 후 맥스가 갱신되지 않았을 때 최대수가 현재수보다 작다면 갱신해주는 부분이다.

BOJ : https://www.acmicpc.net/problem/10989

시간제한 3초, 메모리 제한 8MB

최대 1천만개의 수를 이 시간과 메모리안에 정렬할려면 사실상 sort를 쓰거나 

sort보다 더 빠른 함수를 만들더라도 불가능할 것이다..

이 문제는 최대의 수가 10000 이라는 것이 힌트이다.

1 2 3 4 5 6 ,,, 9998 9999 10000 이라는 숫자가 1천만개 나올 것이므로

배열[10001] 에 나오는 숫자마다 +1 해주어서 카운트 해두고

1부터 1만까지 차례대로 출력해주면 되는 문제이다.

BOJ : https://www.acmicpc.net/problem/10825

구조체 operator 를 사용한 정렬을 해보고 싶은데 할줄 몰라서

일단 bool 함수를 만들어서 해결했다.

operator 함수 공부한 후 재포스팅해야겠다!