minu0122   2년 전

c++로 구현했는데 scanf 하고 printf 가 cin 이나 cout 보다 빠르다고 해서 c 라이브러리 추가해서 사용했습니다. 또한 정렬할때 quicksort로 했는데 시간초과가 뜨길래 quicksort의 최악의 경우를 넣은건가 싶어서 mergesort로 바꾸었는데 아직도 시간초과가 뜹니다. 혹시 조언좀 구할 수 있을까요?

djm03178   2년 전

질문을 올릴 때 위에 읽으라고 나오는 공지사항을 읽으셨나요? 그 글에 굵은 글씨로 적힌 문장을 다시 읽어보시기 바랍니다.

chogahui05   2년 전

더 빠르게 하는 방법

: new랑 delete를 안 쓰면 됩니다.

사실 그냥 L과 R을 전역변수처럼 써 버리면 더 빨라지겠죠. 할당할 필요도 없으니까.

sort 함수를 쓴 경우, 1.5초 정도에 아슬아슬하게 통과했다는 것만 참고하심 됩니다.

그리고

(1) 할당

(2) 복사

(3) merge

(4) 제거

에서 사실상 (1), (4)는 필요가 없죠.

chogahui05   2년 전

O(nlogn)짜리인데, 아슬아슬하게 통과하는 경우

상수를 낮추는 것도 중요해요.

minu0122   2년 전

djm03178님 게시판에서 mergesort를 찾아봤다고 생각했는데 착각이었네요;; 앞으로 좀더 샅샅이 찾아보겠습니다

chogahui05님 조언 감사합니다

minu0122   2년 전

chogahui05님 말씀하신대로 sort도 써보고 직접 quicksort 만들어서 k 값이 있는쪽으로 정렬하는 코드를 만들었는데 결과는 똑같네요ㅠㅠ

혹시 제 코드를 보시고 또 조언이 생각나셔서 댓글 달아주시면 정말 감사하겠습니다

djm03178   2년 전

다른 질문글들을 보면, quickselect (quicksort가 아니라)에 대해 이야기하는 것이 많이 있습니다.

다만 지금은 강력한 데이터가 하나 있어서 평범한 구현으로는 어렵고, 그냥 STL의 nth_element를 쓰는 편이 현명합니다.

그보다 더욱 병목이 되는 것은 입력이니, 입력을 빠르게 받는 법을 찾아보셔도 됩니다.

minu0122   2년 전

둘이 같은것을 의미하고 있는줄 알았는데 제가 잘못 알고 있었군요...또한 더빠르게 입력을 받을 수 있는지 몰랐습니다 더 찾아보고 고민하겠습니다

감사합니다~

djm03178   2년 전

빠른 입력은 이 문제를 풀어보세요.

https://www.acmicpc.net/proble...

minu0122   2년 전

예전부터 입출력이 많으면 scanf와 printf를 자주 사용했는데 cin.tie(null)과 sync_with_stdio(false)가 더 빠른건가요?

저 문제는 scanf와 printf를 사용하여 풀었습니다

djm03178   2년 전

그에 대한 건 https://www.acmicpc.net/blog/v... 에 있습니다.

minu0122   2년 전

좋은 정보 감사합니다 

많이 배우고 가네요ㅎㅎ

chogahui05   2년 전

물론, scanf, printf만 쓰고, nth_element 없이 푸는 방법이 있습니다. 만. 비추천합니다.

더 정확히 말해서, 최악의 경우에 O(2n)짜리도, scanf와 printf만 이용해서 1168ms에 통과했습니다. fast_io는 136ms


상당히 빡빡하니까.

scanf, printf를 쓰실 경우, 다른 방법을 찾아보세요. 그 방법은 제가 알려드릴 수도 있지만. 

스스로 찾아서 공부해 보시는 것도 나쁘지 않을 거 같습니다.

minu0122   2년 전

100~200ms 나오신분들 코드를 보니 입력을 직접 만들어서 쓰시는것 같던데 그러한게 fast_io가 이것을 지칭하는 건가요?

구글링을 많이 했는데 quicksort에 대한 내용이 대부분이던데 참고할 만한 사이트라도 가르쳐주시면 감사하겠습니다.

chogahui05   2년 전

radix sort, intro sort, quick select, intro select, heap 등을 찾아보시면 좋을 거 같습니다.

제가 푼 방법은 1번째고요. 아니면 c++에서 nth_element도 찾아보면 유용한 자료 꽤 있어요..

minu0122   2년 전

모두 처음 들어보는 정렬방식이네요;; 감사합니다

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