htj889   3년 전

점의 개수만큼 입력받고

점의 개수만큼 배열을 동적할당 한 다음에 배열의 맨 앞부터 순서대로 점의 값을 입력받습니다.

그리고 나서 퀵 정렬을 합니다.

kesakiyo   3년 전

피봇을 항상 앞에서 잡지 말고 랜덤한 값으로 잡아보세요

정렬된 상태로 들어온다면 O(N^2)으로 작동할 것 같습니다.

htj889   3년 전

랜덤한 값으로 잡아보았는데도 시간초과가 일어납니다

코드는 이렇습니다. 메인에서 srand(time(NULL)); 도 해주었구요. ㅠㅠ

kesakiyo   3년 전

이 문제는 입출력 양이 많으므로 빠른 입출력을 사용해야 합니다.

cin, cout보다는 scanf, printf를 권장합니다.

mainpower4309   9달 전

시간이 꽤나 오래되어 보실지 모르겠으나....

일단 cin과 cout의 속도를 높이기위해  main에 한줄 선언하였습니다. 또한 줄바꿈 endl은 속도가 느려 '\n'으로 변경하였습니다.

그리고 pivot 잡으실때 배열중에 무작위로 3개 고르고 난뒤 이중에 중간값을 pivot으로 잡으면 좋은 성능이 나옵니다.

괜히 random함수 호출해서 시간 또 잡아먹을 필요가 없죠. 코드 살짝만 바꾸니 잘 실행되고 통과하였습니다.

객체지향으로 너무 잘 푸셔서 저도 코드 보고 배워갑니다....

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