9426번 - 중앙값 측정
단계별로 풀어보기로 이 문제를 접하는 분들은 모든 중앙값을 "부분배열을 뽑아내고, 정렬한 다음 가운데 원소를 얻어내는" 방법으로 푸실 것입니다. 이렇게 하면 시간초과가 납니다. 심지어 퀵셀렉이나 O(K)짜리 정렬 알고리즘을 써도 시간초과가 나오는 것으로 알고 있습니다.
단순히 이름이 "중앙값 측정"이라는 이유로 정렬하기 단계에 있는 건 아닌지 확인 부탁드립니다.
처음에 K개를 정렬하고 들어가는 알고리즘도 있긴 하지만 그게 핵심은 아닐 거고... 제 코드 하나 읽으셨듯이 O(NK)짜리가 가까스로 통과될 수도 있는데 이건 데이터가 약해서인 거 같으니 확실히 이 문제가 정렬이 중심이 되는 건 아닌 것 같습니다.
정렬하기에서 삭제했습니다.
댓글을 작성하려면 로그인해야 합니다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
한국어 | English (Beta)
AltStyle によって変換されたページ (->オリジナル) / アドレス: モード: デフォルト 音声ブラウザ ルビ付き 配色反転 文字拡大 モバイル
jh05013 8년 전 1
단계별로 풀어보기로 이 문제를 접하는 분들은 모든 중앙값을 "부분배열을 뽑아내고, 정렬한 다음 가운데 원소를 얻어내는" 방법으로 푸실 것입니다. 이렇게 하면 시간초과가 납니다. 심지어 퀵셀렉이나 O(K)짜리 정렬 알고리즘을 써도 시간초과가 나오는 것으로 알고 있습니다.
단순히 이름이 "중앙값 측정"이라는 이유로 정렬하기 단계에 있는 건 아닌지 확인 부탁드립니다.