debuglog   2년 전

quick selection으로 풀려고 하는데 잘안되네요 ㅠㅠ

피벗위치를 바꿔보기도 했는데 마찬가지입니다.


다른 접근방식이 있을까요?

jh05013   2년 전

모든 입력에 대해 시간 안에 돌아가야 하므로 최악의 경우도 고려해야 합니다.

피벗 위치를 랜덤으로 하면 돌아가려나요?

debuglog   2년 전

랜덤으로 바꾸고 돌려봤는데도 계속 시간초과가 뜨네요 ㅠ.ㅠ

jh05013   2년 전

입력의 크기 상으로 Quick selection으로는 안 될 것 같네요. N*K보다 빠르게 푸는 방법이 있습니다. (구간트리, 이진 탐색 트리 등) 솔직히 이게 9단계에 있을 만한 문제는 아닌 것 같습니다.

debuglog   2년 전

감사합니다! 나중에 다시 풀어봐야게네요ㅠ

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