[C] 백준 1920번: 나의 첫 퀵 소트와 이진 탐색

📎 백준 1920번 풀러 가기

1920번: 수 찾기

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 $ 2^{-31} $ 보다 크거나 같고 $ 2^{31} $보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

---

이 문제도 예전에 풀었다가 실패했던 문제이다.

문제만 보면 굉장히 쉽다고 느껴질 수도 있는 문제이다.

 

나도 처음에 그렇게 생각했었다.에, 이거 for문 두 번만 돌리면 되는거 아냐?

 

그러나 자료구조를 조금이라도 공부했다면 알 것이다.

for문을 두 번 돌리게 되면 시간 복잡도는 $ O(n^2) $ 이 되는데,

N과 M값의 최대값이 $ 10^5 $ 이므로, 엄청난 시간이 걸리게 되는 것이다.

 

그럼 이 시간을 줄일 방법이 무엇이 있을까🤔🤔

 

대표적인 예로 이진 탐색이 있다.

이진 탐색은 시간복잡도가 $ O(log_2{n}) $이므로

걸리는 시간이 현저하게 줄어드는 것을 알 수 있다.

 

그래서 여기서는 이진 탐색을 활용하였다.

이진 탐색은 개념만 알고 있고,

실제로 코드로 구현해본 것은 이번이 처음이라

약간의 구글링의 도움을 받았다.

 

그리고 중요한 점!

이진 탐색은 정렬된 리스트에서 활용하는 방법이므로,

이진 탐색을 하기 전, 리스트를 정렬을 해줄 필요가 있다.

 

정렬에는 굉장히 많은 방법이 있다.

삽입 정렬, 버블 정렬, quick sort, merge sort 등등...

 

나는 시간 복잡도가 작은 퀵 소트를 사용해서 정렬을 하기로 했다.

퀵 소트는 divide and conquer의 방법 중 하나인데,

평균적으로 $ O(nlog{n}) $의 시간 복잡도를 가지지만,

최악의 경우 시간 복잡도는 $ O(n^2) $이기 때문에

주의해서 사용을 할 필요가 있다.

 

퀵 소트는 C의 stdlib.h에 이미 구현이 되어있기 때문에,

compare함수만 따로 구현을 해주어 퀵 소트를 하였다.

 

1학기 때 자료구조 수업을 들을 때,

코딩 테스트 문제로 퀵 소트를 사용하는 것이 나왔는데

그때는 잘 못했었지만....^^

오늘은 제대로 구현을 했다.

 

이때, 매개변수를 const void* 로 넘겨주는데,

이는 void형 상수를 가리키는 포인터라는 뜻이다.

즉, 포인터이기 때문에 함수 내에서 매개변수의 값을 마음대로 바꾸면 안 된다.

---

아래는 내가 구현한 코드👇

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b)
{
    return *(int*)a > *(int*)b ? 1 : (*(int*)a < *(int*)b ? -1 : 0);
}

int binary_search(int arr[], int num, int size)
{
    int front, rear, pivot;
    front = 0;
    rear = size - 1;
    while (1) {
        pivot = (front + rear) / 2;
        if (arr[pivot] == num) return 1;
        if (arr[front] == num) return 1;
        if (arr[rear] == num) return 1;

        if (arr[pivot] < num)
            front = pivot + 1;
        else 
            rear = pivot - 1;
        if (front >= rear)
            return 0;
    }
}

int main(void){
    int n;
    scanf("%d", &n);
    int *arr = (int*)malloc(n * sizeof(int));

    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    int m;
    scanf("%d", &m);
    int *arr2 = (int*)malloc(m * sizeof(int));

    for(int i = 0; i < m; i++){
        scanf("%d", &arr2[i]);
    }

    qsort(arr, n, sizeof(int), compare);

    for(int j = 0; j < m; j++){
        printf("%d\n", binary_search(arr, arr2[j], n));
    }
    return 0;
}

---

✍새로 안 사실들

1. 이진탐색은 시간복잡도가 $ O(log_2{n}) $이다.

2. 이진탐색을 쓰기 전에 먼저 탐색하고자 하는 리스트를 정렬해주어야 한다.

3. 퀵 소트는 C에서 stdlib.h에 qsort()라는 함수로 구현되어 있다.

     형태는 다음과 같다.

     qsort(정렬할 메모리 주소(또는 배열 이름), 정렬할 요소의 개수, 요소 크기, 비교 함수);

      퀵소트는 평균적으로 $ O(nlog{n}) $의 시간 복잡도를 가지지만, 

      최악의 경우 시간 복잡도는 $ O(n^2) $이므로,

      주의해서 사용을 할 필요가 있다.

4. const void *는 void형 상수를 가리키는 포인터라는 뜻이다.

    -> compare 함수 내에서 포인터의 값을 마음대로 바꾸면 큰일 난다.