11004번 - K번째 수
예전에는 우선순위큐를 이용한 힙 구현으로 문제를 풀었는데
학교에서 LinearSelect이라고 하는 선형시간이 걸리는 알고리즘을 배워서 그걸 적용 해보았더니, 21%까지는 잘가다가 거기서 시간초과가 뜨더라구요.
혹시 시간복잡도에 대해 자세히 아시는 분들 설명좀 해주실수 있나요 ??? 일단 최악의경우도 n 이라더라구요 리니어 셀렉이
힙은 nlogn이라고 알고있는데도 답이 뜨는데 흠 ..
O(n)이 맞긴 한데, 성능 향상을 보려면 좀 구현에 공을 많이 들여야 할거에요
일단 학교에서 사용하는 저지에서는 리니어셀렉의 구현에대한 문제에 어셉을 받아서 내보았는데 시간초과가나네요 ㅠㅠ
전 linear selection algo에 대해서 잘 몰라서, 그걸 도움드리긴 힘들거 같고
다만 흑마법 (?) 이라고 하면, 아마 입력을 scanf로 해도 많이 느릴텐데, 제 0.1 소스를 한번 참고해서 빠르게 입력받아보세요. 백점이 아니어도 제 소스는 받을 수 있어요
댓글을 작성하려면 로그인해야 합니다.
wjdtmdrbs88 8년 전
예전에는 우선순위큐를 이용한 힙 구현으로 문제를 풀었는데
학교에서 LinearSelect이라고 하는 선형시간이 걸리는 알고리즘을 배워서 그걸 적용 해보았더니, 21%까지는 잘가다가 거기서 시간초과가 뜨더라구요.
혹시 시간복잡도에 대해 자세히 아시는 분들 설명좀 해주실수 있나요 ??? 일단 최악의경우도 n 이라더라구요 리니어 셀렉이
힙은 nlogn이라고 알고있는데도 답이 뜨는데 흠 ..