[BOJ알고리즘, C++]#10815_숫자 카드, 이진 탐색, Binary Search

[BOJ 알고리즘, C++] #10815_숫자 카드, 이진 탐색, Binary Search

 

BOJ 알고리즘 문제 풀이, 10815_숫자 카드

이분 탐색을 통해 주어진 숫자 카드가 존재하는지 탐색합니다.

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

 

#2. 풀이

 

1. 이진 탐색(Binary Search)

 

Details

 

1. [정의] : 정렬된 원소 목록을 반으로 나누어 찾고자 하는 원소와 중심이 되는 원소를 비교하고, 작다면 왼쪽으로 크다면 오른쪽으로 중심 원소를 옮겨서 반복적으로 비교 작업을 수행합니다. 시간 복잡도는 O(log  n)으로 선형 탐색보다 뛰어난 성능을 보여줍니다! 다만 몇 가지 단점들이 물론 존재합니다!
2. [특징] : 정렬 상태의 자료구조에서만 가능합니다. 그리고, 연결 리스트에서 사용이 힘듭니다.

 

#3. 코드

/*
    설명:
        Binary Search를 사용합니다.
    풀이:
        1. 먼저 숫자 카드를 오름 차순(less) 정렬 합니다.
        2. left = 0, right = N-1, mid = (left + right)/2
        3. 정수를 mid와 비교하고, mid보다 작다면 right = mid-1 로 변경, mid보다 크다면 left = mid+1로 설정
        4. 퀵 정렬하고 비슷하지만, 정확하게는 Pivot을 정하며 잘게 잘게 분할 하는 과정을 통해 마지막에 다다르면 정답을 찾는 풀이입니다.
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, M;
    vector<int> nVector; vector<int> mVector;

    cin >> N;
    for(int i=0; i<N; i++)
    {
        int tmp;
        cin >> tmp;

        nVector.push_back(tmp);
    }

    cin >> M;
    for(int i=0; i<M; i++)
    {
        int tmp2;
        cin >> tmp2;

        mVector.push_back(tmp2);
    }

    sort(begin(nVector), end(nVector));

    for(int i=0; i<M; i++)
    {
        int right = N-1;
        int left = 0;
        bool check = false;
        while(left <= right)
        {
            int mid = (left + right)/2;
            if (mVector[i] == nVector[mid])
                check = true;
            if (mVector[i] < nVector[mid])
                right = mid-1;
            else
                left = mid+1;
        }

        if(check == true)
            cout << 1 << " ";
        else
            cout << 0 << " ";
    }
}