square99   2년 전

Quick Selection 직접 구현, nth_element, multiset 다 써봤습니다만, 5%에서 시간초과를 넘길수가 없네요 ㅜㅜ

Quick Selection, nth_element는 원래의 데이터가 섞이기 때문에 이를 방지하기 위해서 추가 배열에 데이터 복사하느라

O(nk) 이상 되는 것같고,

multiset은 random access가 안되서 중간값 찾느라 iterator 연산시간 때문에 또 타임아웃 나는듯 한데요,

고수 분들의 도움을 요청합니다~

chogahui05   2년 전

12번 트라이 해서 겨우 성공했네요.. 아이디어는 금방 나왔는데..


하.. STL은 초보인지라.. 뭐가 뭔지도 모르겠고요. 세그먼트 폴트가 계속 나고.. 그럽니다.

일단 힌트가 될 수 있는 것은 데이터 사이즈가 25만이나 되기 때문에 O(nlogn)짜리 알고리즘을 써야 하고요.

이 문제의 접근법은 여러 가지가 있습니다.. 일단 rb tree를 직접 구현하는 방법이 있어요.

그런데. 이건 매우 힘들지요. 버블 정렬 문제를 rb tree를 직접 구현해서 풀어보는게 이번 달 과제인지라..


문제에서 구하고자 하는 것을 먼저 봅시다. 밑에 코드를 보면 아시겠지만..

왼쪽을 [k/2], 오른쪽을 k-[k/2]개로 분할했을 때, k가 짝수일 때와 홀수일 때가 다릅니다. 이게 1번째 힌트.


2번째는 n이 1, 2, 3일 때는 굳이 트리에 안 넣어도 해결 가능하다는 것.

STL에 익숙하지 않으시다면 오히려 2번째 힌트가 더.. 쓸만할 지도 모르겠네요.


3번째는.. 경우의 수.

이 정도만 알려드리면 될 거 같네요.

chogahui05   2년 전

multiset은 random access가 안되서 중간값 찾느라 iterator 연산시간 때문에 또 타임아웃 나는듯 한데요,

이게 핵심입니다. 노드가 연속적으로 저장이 되어 있지 않고..

마치 트리? Linked List처럼 띄엄 띄엄 연결이 되어 있거든요. 랜덤 억세스가 가능하려면

연속적으로 저장이 되어 있어야 하는데.. 안 그러니까요.

square99   2년 전

덕분에 해결했습니다~ 감사합니다

문제 풀고 다른 분들 코드 보니 정말 부끄럽게 풀어놨네요.

STL 대충 알고 대충 쓰고 있었는데 이번에 많이 배웠네요

chogahui05   2년 전

C++ STL은 저도 초보라서요.

STL은 C로 직접 자료구조를 구현하기 싫어서 쓰는데요. 가끔. STL 쓰다가 잘 안 되면

그냥 C로 구현합니다.. 이 문제도 계속되는 세그멘테이션 폴트로 그럴 뻔 했지만..


java의 sort도 매우 작은 숫자에 대해서는 간단한 알고리즘을 적용하잖아? 라는 생각을 하게 되니.

어렵지 않게 바뀌었습니다.

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