백준 1920번 C, C++ 풀이

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

처음으로 풀어보는 탐색문제이다. 처음에는 탐색알고리즘이라는걸 모른 채로 그냥 for문 계속 돌리면서 풀었는데, 역시나 시간초과가 나오고 포기했던 문제이다. 하지만 이진탐색(binary search) 알고리즘을 알게 되어 이 문제를 다시 풀었고 맞췄다.

 

이진탐색은 생각보다 우리가 자주 쓰는 알고리즘이다. 0~100부터 아무 숫자나 하나 정하고, 업다운 게임을 진행한다고 하자. 이를 맞추라고 하면 당신은 어떻게 할 것인가? 게임좀 해본 사람이라면 일단 0과 100사이의 값인 50을 외치고, 업 다운 힌트를 통해 절반값을 계속 찾아나갈 것이다. 이와 굉장히 유사하다.

 

하지만 이진탐색을 진행하기 위해서는 배열이 정렬되어있어야 한다. 안그러면 중간값을 잘 찾아들어가도 찾고자 하는 값을 제대로 찾기 힘들 것이니 말이다.

// C sol
#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) { // 정렬함수
    int num1 = *(int *)a;
    int num2 = *(int *)b;

    if (num1 < num2)
        return -1;
    
    if (num1 > num2)
        return 1;      
    
    return 0;
}

int myBsearch (int arr[], int start, int end, int target) {
    if (start > end) return -1;
    int mid = (start + end) / 2;
    if (arr[mid] > target) return myBsearch(arr, start, mid-1, target);
    else if (arr[mid] < target) return myBsearch(arr, mid+1, end, target);
    else return mid;
}

int main () {
    int len;
    int n;
    int temp;
    int * arr;
    
    scanf("%d", &len);
    arr = (int *)malloc(sizeof(int) * len);
    for (int i = 0; i < len; ++i) scanf("%d", &arr[i]);
    qsort(arr, len, sizeof(int), compare);

    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &temp);
        if (myBsearch(arr, 0, len, temp) != -1) printf("1\n");
        else printf("0\n");
    }
}

C++의 경우 algorithm 헤더에 기본적으로 이진탐색에 관한 함수가 정의되어있다. binary_search 함수는 이름에서 볼수 있다 싶이 이진탐색 함수이다. 단 이 함수는 들어있는지만 판단하고 위치는 파악하지 못한다. 그래서 값을 찾는 함수는 lower_bound함수와 upper_bound함수를 통해 찾을 수 있다.

// C++ sol
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, temp;
    vector<int> v;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        v.push_back(temp);
    }
    sort(v.begin(), v.end());
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> temp;
        cout << binary_search(v.begin(), v.end(), temp) << '\n';
    }
}