글 읽기 - 퀵정렬을 구현했는데 시간초과가 나옵니다.

bbbjihan 2년 전 0

퀵정렬 + 이진탐색을 통한 문제해결을 하려 하였으나

직접 둘 다 구현하여 실행하니 시간초과가 발생합니다.

둘 중에 어느 함수가 문제인지 확인하기 위해 퀵정렬을 대신하여 algorithm 헤더에서 제공하는 sort를 적용해보았는데 이는 시간초과가 발생하지 않고 통과됩니다.

그럼 제 퀵정렬이 문제가 있다는 것 같은데, 구글링해서 찾아본 코드들과 별반 다를 것이 없어 보입니다. 무엇인 문제인지 모르겠습니다.

아니면 이 문제는 직접 정렬하면 틀리는 문제인 것인가요? 퀵정렬로 푸신 분도 계신 것 같은데...

#include <iostream>
#include <algorithm>
using namespace std;

int quicksort(int array[], int start, int end){
  if(start>=end) {return 0;} // 배열 길이가 0 또는 1인 경우 리턴

  int pivot = array[start];
  int tmp_l = start + 1;
  int tmp_r = end;
  //array의 첫번째 값을 pivot으로, 그 다음 인덱스를 left temp값, 마지막 인덱스를 right temp값으로 할당

  while(tmp_l<=tmp_r){  //인덱스 포인터가 엇갈릴 때까지 반복
    while(array[tmp_l]<=pivot && tmp_l<end){
      tmp_l++;
    }
    while(array[tmp_r]>pivot && tmp_r>start){
      tmp_r--;
    }
    if(tmp_l>tmp_r){swap(array[start],array[tmp_r]);}//엇갈리면, pivot값을 올바른 위치로 swap
    else{swap(array[tmp_l],array[tmp_r]);}//왼쪽값 중 pivot보다 큰 값, 오른쪽값 중 pivot보다 작은 값을 발견할 때마다 swap해줌.
  }  

  quicksort(array,start,tmp_r-1);
  quicksort(array,tmp_r+1,end);
  //모든 분할구간에서 실행되도록 재귀호출

  return 0;
}

int binarysearch(int array[], int len, int target){
  int low = 0;
  int high = len-1;
  int mid;

  while(high>=low){
    mid = (low+high)/2;

    if(array[mid]==target){
      return 1;
    }
    else if(array[mid]>target){
      high = mid-1;
    }
    else if(array[mid]<target){
      low = mid+1;
    }
  }

  return 0;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  int n = 0;
  cin>>n;
  int target[n]{};
  for(int i = 0; i<n; i++){
    cin>>target[i];
  }

  int m = 0;
  cin>>m;
  int finding[m]{};
  for(int i = 0; i<m; i++){
    cin>>finding[i];
  }

  quicksort(target,0,n-1);

  for(int i = 0; i<m; i++){
    cout<<binarysearch(target, n, finding[i])<<"\n";
  }
}

lcr7324 2년 전 1

퀵소트의 피봇을 배열의 첫 번째 값으로 잡는 경우에 시간복잡도가 O(n^2)이 되게 하는 저격 데이터가 있는 것으로 알고 있습니다.

bbbjihan 2년 전 0

답변 감사드립니다.

그렇다면 이 문제는 퀵소트를 직접 사용하지 못하게 하려고 테스트케이스가 구성되어 있다는 것인데, 이 문제는 어떤 정렬법을 사용해야 시간복잡도를 최소로 줄일 수 있는 건가요?

힙소트를 해야할까요?

lcr7324 2년 전 2

퀵소트를 하되 피봇을 랜덤으로 선택하는 방법이 있고, O(nlogn)의 시간 복잡도가 보장되는 정렬 알고리즘을 사용하는 방법도 있겠습니다. 말씀하신 힙소트도 그 중 하나겠네요.

bbbjihan 2년 전 0

친절한 답변 감사드립니다! 궁금한 점이 확실하게 해결됐습니다...! 복받으세요 선생님!

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

문제

문제

출처

ICPC

퀵정렬을 구현했는데 시간초과가 나옵니다.

bbbjihan 2년 전 0

lcr7324 2년 전 1

bbbjihan 2년 전 0

lcr7324 2년 전 2

bbbjihan 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말