문제 푼 날짜 : 2021-07-17

문제

문제 링크 : https://www.acmicpc.net/problem/1920

접근 및 풀이

Binary Search(이진탐색)을 공부할 수 있는 기본문제이다.
정렬된 배열의 가운데 값을 기준으로 찾고자 하는 값과의 대소 관계에 따라서 범위를 좁혀나가게 된다. 그렇기 때문에 이진탐색은 정렬이 되어있는 배열에서 특정한 값을 O(log n) 안에 찾을 수 있는 알고리즘이다.

코드

// 백준 1920번 : 수 찾기
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> vec;

int binarySearch(int num) {
    int first = 0, last = N - 1;
    while (first <= last) {
        int mid = (first + last)/2;
        if (vec[mid] == num) {
            return 1;
        }
        if (vec[mid] < num) {
            first = mid + 1;
        } else {
            last = mid - 1;
        }
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) {
        int input;
        cin >> input;
        vec.push_back(input);
    }
    sort(vec.begin(), vec.end());
    
    cin >> M;

    for (int i = 0; i < M; i++) {
        int num;
        cin >> num;
        cout << binarySearch(num) << '\n';
    }
    return 0;
}

결과

시간초과는... 이것저것 뻘짓을 좀 해보다가...ㅎㅎ

피드백

코딩테스트를 공부하면서 난이도가 낮은 문제가 아니면 대부분이 값을 찾기 위해서는 기본적으로 이진 탐색을 적용하는 것을 알게 되었다.
그래서 다시 한 번 이 알고리즘의 개념을 정확히 알고 있어야 할 필요성을 느껴서 문제를 풀어보게 되었다.