자료구조의 중요성(퀵 정렬, 이진 탐색의 이용)

나열된 두 종류의 수가 있다고 생각해보자.

ex) 

9 2 1 4 5 

2 3 5 6 1

9 2 1 4 5는 나열된 수이고

2 3 5 6 1을 통해 위의 수가 있다면 1 없다면 0을 출력해야 한다.

즉, 2는 위에 있으니 1, 3은 없으니 0, 5는 있으니 1, 6은 없으니 0 1은 있으니 1

1 0 1 0 1이 출력된다.

이 알고리즘을 짤때 바로 생각드는건 2중 for문을 이용하여 9를 지정하고 2~1까지 조사하는법을 생각 해 볼 것이다.

하지만, 수의 개수가 많아지면 어떻게 될까?

시간복잡도 O(n)은 상상 할 수 없을정도로 커질 것이다.

어떤 방법이 있을까 생각해보면

위의  9 2 1 4 5를 Quick Sort(퀵 정렬)로 정렬하고

아래의 값들을 Binary Search(이진 탐색)을 이용하여 찾는다면

시간 복잡도가 확실히 줄어들 것이다.

(물론 퀵의 최악과, 이진의 최악상태로 있다면 O(n)이 늘어나겠지만, 2중 for문보다는 어떻게 해도 O(n)은 낮다.)

 
#include <stdio.h>
 
void Swap(int arr[], int a, int b); // a,b 스왑 함수 
int Partition(int arr[], int left, int right);
void QuickSort(int arr[], int left, int right);
 
 
int arr[1000005] ={0,};
 
int main()
{
 int tCase; // 테스트 케이스 
 int i,j,n,k,tmp; // i,j = for문 변수, n,k = 몇가지 숫자 입력받을지 
 int check = 0; // 바이너리 서치 통과되면 check = 1 아니면 check = 0 
 
 int first = 0; // 이진 탐색 변수  
 int last = 0;
 int middle = (first + last) / 2;
 
 scanf("%d",&tCase);
 
 for(tCase ; tCase > 0 ; tCase --)
 {
  scanf("%d",&n);
  
  for(i = 0 ; i < n ; i ++)
  {
   scanf("%d",&k);
   arr[i] = k;
  }
  
  QuickSort(arr,0,n-1); // 퀵정렬로 위의 상태 정렬 
  
  tmp = n; // ex)위의 수가 5가지고 아래 수가 4가지면 바이너리 서치 에러나니 tmp에 저장
   
  scanf("%d",&n);
  
  for(i = 0 ; i < n ; i ++)
  {
   scanf("%d",&k);
   
   // 여기서 부터 바이너리 서치로 조사한다. 
   first = 0;
   last = tmp-1;
   middle = (first + last)/2;
 
  while(first <= last)
  {
   middle = (first+last)/2; // 탐색 대상의 중앙을 검색
  
   if(k == arr[middle]) // 중앙에 저장된 것이 타겟이라면
   {
    printf("1\n");
    check = 1;
    break; // 탐색 완료
   }
  
   else // 타겟이 아니라면 탐색 대상을 반으로 줄인다.
   {
      if(k < arr[middle]) 
      { last = middle-1; }
 
      else
      { first = middle+1; }
   
   }
 
 } // while end
  if(check == 0) // 탐색 실패 
  {
   printf("0\n");
  }
  check = 0; // 다시 초기화 
         
  } // for end
  
 } // tCase end
 
} // main end
 
 
 
 
 
 
// 퀵정렬 이용 
void Swap(int arr[], int a, int b) // a,b 스왑 함수 
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}
 
int Partition(int arr[], int left, int right)
{
    int pivot = arr[left]; // 피벗의 위치는 가장 왼쪽에서 시작
    int low = left + 1;
    int high = right;
 
 
    while (low <= high) // 교차되기 전까지 반복한다 
    {
        while (pivot >= arr[low] && low <= right) // 피벗보다 큰 값을 찾는 과정 
        {
            low++; // low를 오른쪽으로 이동 
        }
 
        while (pivot <= arr[high] && high >= (left+1) ) // 피벗보다 작은 값을 찾는 과정 
        {
            high--; // high를 왼쪽으로 이동
        }
 
        if (low <= high)// 교차되지 않은 상태이면 스왑 과정 실행 
        {
            Swap(arr, low, high); //low와 high를 스왑 
        }
 
    }
    Swap(arr, left, high); // 피벗과 high가 가리키는 대상을 교환 
    return high;  // 옮겨진 피벗의 위치정보를 반환 
 
}
 
 
void QuickSort(int arr[], int left, int right)
{
    if (left <= right)
    {
        int pivot = Partition(arr, left, right); // 둘로 나누어서
        QuickSort(arr, left, pivot - 1); // 왼쪽 영역을 정렬한다.
        QuickSort(arr, pivot + 1, right); // 오른쪽 영역을 정렬한다.
    }
}
 
 
 
 
 
 

자료구조를 배워야 하는 이유와, 어떻게 응용해야 되는지가 이 코드에 담겨 있는 것 같다.