zxzimin   3년 전

정말 의문입니다..

sync_with_stdio(false)랑 cin.tie(false)도 설정해줬는데 어디가 문제일까요..?

quick selection 함수 자체에 문제가 있을까요?

Green55   3년 전

질문 검색을 먼저 해서 자신에게 필요한 답변이나 반례가 없는지 확인하고 질문을 남겨주세요.

왜 시간초과인지는 https://www.acmicpc.net/board/view/36672 에 잘 나와있습니다.

3. 오히려 quickselect의 경우 잘 구현하지 않으면 quicksort와 마찬가지로 피벗이 한쪽으로 쏠리는 문제가 발생하여 최악의 경우 O(N^2)이 됩니다. 

zxzimin   3년 전

확인하고 올바르게 구현했다고 생각했는데 그게 아닌가 보군요 ㅜㅜ

Green55   3년 전

퀵 셀렉션에 일반적인 구현은 최악 O(n^2)이고, 이 코드 역시 매우 일반적인 코드이기 때문에 시간초과가 난 것입니다.

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