husy951   4년 전

퀵소트를 이용해서 빠른 정렬 이후 K번째 숫자를 출력하는 소스입니다.

그런데도 시간초과라니요.. ㅠ

onjo0127   4년 전

scanf보다 상대적으로 느린 cin으로 백만개 정도의 수를 입력받기 때문에 시간초과가 날 수 있습니다.

시작 부분에 ios::sync_with_stdio(false);를 넣어주시면 빨라질거에요 ㅎ

그리고 퀵정렬은 평균 O(NlogN)의 시간복잡도를 가지지만, 최악의 경우에는 O(N^2)이 걸립니다. 이걸 고쳐도 시간초과가 나면 다른 정렬을 찾아보세요...

husy951   4년 전

@onjo0127

아 ㅁ.... 문제를 잘못 질문했네요 이 문제가 아닌데... ㅎㅎ 이 문제는 맞았습니다.

onjo0127   4년 전

K번째 수 문제 맞나요? ㅎㅎ

quick seletion이라는 알고리즘을 찾아보세용

husy951   4년 전

@onjo0127

네 맞습니다! 알려주신 방법으로 맞았네요 :)

husy951   4년 전

@onjo0127

그런데 알려주신 ios:: ~~ 이건 어떤 방식이길래 속도가 빨라진겁니까???

onjo0127   4년 전

iostream 입출력이 느린 이유가 stdio헤더와 동기화하는 과정 때문에 그런데, 동기화를 꺼주면 빨라지가든요 ㅎㅎ 저코드가 동기화 꺼주는 코드고용

대신 stdio헤더는 같이 못쓰게 되고요

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