justking   4년 전

시간 초과가 떠서그러는데 저만그런거에요?
 stl 의 sort 안쓰고거의  quick sort, merge sort로 풀었던데 이걸로는 원래 못푸는건가요?

kyhdudgns113   4년 전

1. 첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다.     배열의 크기가 백만이 넘어야하는데, 십만을 하셨네요!

justking   4년 전

헐 그런거였네요 정말 감사합니다ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 그런데 stl sort는 시간복잡도가 어떻게되요?

그리고 프로그래밍 대회 이런데서 쓸수있어요??

kyhdudgns113   4년 전

qsort 는 최악의 경우 n^2 이고, stl sort 는 nlogn 입니다.

stl 을 쓰지 말라고 하면 못쓰겠지만, 굳이 그럴까요...?

justking   4년 전

ky님 말대로라면 qsort는 별로 안좋다는얘기네요.. 그럼stl sort가 더간편하고 빠른데 qsort쓰는 사람들은 왜 쓰까요? 그냥 자기만족인가요/??

okaybody5   4년 전

sort가 C++의 STL이라 C 쓰는사람은 qsort를 쓸수도..?

donghoon0709   4년 전

stl sort는 퀵정렬로 구현되어있는걸로 알고 있는데요...

stl stable_sort는 병합정렬로 구현되어있어 항상 nlogn이 걸립니다.

kyhdudgns113   4년 전

donghoon 님 말씀대로 sort 함수는 퀵정렬로 구성되어있습니다! 
대신 sort 함수는 분할이 최악으로 일어날때, 이를 대비하기 위한 장치가 있습니다. 그래서 시간복잡도가 거의 nlogn 이 나옵니다.
적어도 제가 백준에서 풀었던 문제들 중에서는 sort 함수를 씀으로서 시간초과가 난적은 없었습니다!

jwvg0425   4년 전

stl의 정렬 알고리즘은 정확히 말하자면 퀵 소트가 아닙니다. 엄밀히 말하자면 intro sort라는 알고리즘을 쓴다고 말할 수 있습니다. 

앞서 말씀해주신 것처럼 최악의 경우에도 O(nlogn)을 유지해주기 위한 변형이 가해진 알고리즘이고, 그래서 정확히는 퀵소트라고 말할 수 없는 알고리즘이죠(엄밀히 따지자면 동작이 다른 알고리즘이므로).  비교 기반의 정렬 알고리즘은 이보다 더 빠를 수 없고, stl sort 구현이 속도가 느린 구현이 아니기 때문에 일반적으로 정렬이 필요한 상황에서는 그냥 쓰시면 됩니다. 이 문제의 경우 sort가 느려서 안 쓴 사람이 많다기 보다는 정렬 알고리즘 구현을 한 번 연습해보고자 하는 용도로 직접 구현해 보신 분들이 많은 거 일 거에요.

introsort에 대한 자세한 내용은 위키 피디아 참조해보시면 될 것 같습니다.

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