djm03178   4년 전

  1. 이 문제의 본래 의도는 단순히 정렬을 해서 K번째 수를 빼오는 것이 아닌 것으로 추정됩니다. N이 지나치게 커 보이는 건 이 때문입니다. 이 문제의 의도대로 문제를 풀고 싶으시다면 quickselect(quicksort가 아니라)라는 알고리즘을 공부해야 합니다. 정렬을 해서 O(NlogN)에 해결하는 것이 아닌, O(N)에 문제를 해결할 수 있게 됩니다.
  2. 하지만 안타깝게도 이 문제에는 허점이 많습니다. O(NlogN)의 정렬보다도 일반적으로 훨씬 더 큰 비중을 차지하는 것은 바로 입력 시간입니다. 입력 시간만 단축해도 정렬로 손쉽게 해결이 가능합니다. 단순히 정렬로 문제를 해결하고 싶으시다면, https://www.acmicpc.net/proble... 를 보고 언어별로 입력 시간을 단축하는 법을 알아보세요.
  3. 오히려 quickselect의 경우 잘 구현하지 않으면 quicksort와 마찬가지로 피벗이 한쪽으로 쏠리는 문제가 발생하여 최악의 경우 O(N^2)이 됩니다. 물론 quicksort로 정렬을 할 때에도 마찬가지입니다.  https://www.acmicpc.net/board/view/31887 를 참고하세요.
  4. 이론적으로 quickselect는 worst case O(N)이 가능하지만, 항상 O(N)을 보장하기 위한 평균 케이스의 오버헤드가 너무 크기 때문에 C++에서는 최악의 경우 O(NlogN) 이상만 보장해줄 것을 명시하고 있습니다. 이를 구현한 함수가 nth_element입니다.

skaduddn   4년 전

quick sort와 quick select 가 다르다는 것을 덕분에 알게되었습니다~~

감사합니다!!

다만 궁금한 것은 c++ algorithm 헤더에 들어있는 sort로 제출하였는데 시간초과가 아니라 틀렸습니다로 나오는 이유가 궁금합니다!

djm03178   4년 전

구현에 오류가 있거나 배열 크기를 잘못 설정하는 등의 실수가 있었을 것입니다.

skaduddn   4년 전

아 그렇군요 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.