kmm7923   4년 전

퀵정렬이 병합정렬보다 빠른건 알고있었는뎅

병합도 nlogn인뎅 merge sort로는 시간안에 할 수 없는건가요??

djm03178   4년 전

nlogn에 풀면 보통은 통과가 힘듭니다. 가까스로 되는 경우도 있다고는 하는데, 문제의 의도가 nlogn이 아닙니다. quick selection이라는 알고리즘을 써야 하는데, 이를 이용하면 평균 O(n)에 풀 수 있습니다. 최악의 경우가 O(n^2)이 되기는 하지만 그 정도의 테스트 케이스는 주지 않는 듯합니다.

CHULMING   4년 전

n번째 element 를 구하는 알고리즘이 있습니다
c++ stl에 nth_element가 구현되어 있기도 하구요.

저는 예전에 이런 알고리즘을 몰라서  heap sort를 k번 진행해서 풀었네요..

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