je4297   2년 전

퀵으로 풀었는데 시간초과가 납니다.

스캐너가 문제라고 해서 bufferedReader랑 bufferedWriter로 바꿨는데도 해결되지 않아 질문을 드립니다.

퀵으로 이 문제가 해결되긴 하는걸까요?

djm03178   2년 전

문제 번호를 적는 칸이 따로 있습니다. 거기에 문제 번호를 적어 주세요.

퀵 소트는 최악의 경우 시간복잡도가 O(n^2)입니다. 그리고 그 최악의 경우를 만들기 너무 쉽습니다. 그래서 naive한 퀵 소트는 정렬에 쓰지 않는 것이 좋고, 내장 라이브러리 함수를 쓰는 게 제일 좋습니다.

kipa00   2년 전

정말로 이 문제를 퀵 소트로 풀고 싶으시다면,

  • 피봇을 랜덤으로 골라야 합니다. 항상 특정 위치의 피봇을 고르게 구현하는 경우, 쉽게 최악의 경우가 걸리는 테스트 케이스를 만들 수 있기 때문입니다.
  • 피봇과 같은 값은 재귀적으로 처리하지 않도록 해야 합니다. 퀵 소트의 특성상 피봇과 같은 값들은 항상 한쪽 구간으로 쏠리게 됩니다. 따라서 모든 값이 같은 경우 최악의 시간이 걸립니다. 피봇보다 작은 것과 큰 것의 개수를 세어 피봇이 들어갈 위치를 구간으로 찾은 뒤, 그 구간을 모두 피봇과 같은 값이 되도록 자리바꿈한 후 처리하는 것이 좋습니다.

퀵 소트는 시간 복잡도가 n log n의 상수 배일 확률이 매우 높은 것을 이용하는 확률적 알고리즘이기 때문에, 엣지 케이스를 잘 생각해서 그 경우를 모두 처리하게 코드를 작성하셔야 합니다.

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