10주차(이진탐색) - [C++]백준10815 숫자 카드

19 May 2022 in Study on Algorithm

백준10815 숫자 카드 링크

문제

예제 입력

---

코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> arr;
vector<int> key;
int n, m;

bool Binary_Search(int key) {
    int st = 0;
    int end = arr.size();

    while (st <= end) {
        int mid = (st + end) / 2;
        if (arr[mid] == key) {
            return true;
        }
        else if (arr[mid] > key) {
            end = mid - 1;
        }
        else {
            st = mid + 1;
        }
    }
    return false;
}

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

    int a;
    cin >> n;
    // vector<int> arr(n);
    for (int i = 1; i <= n; i++) {
        cin >> a;
        arr.push_back(a);
    }
    sort(arr.begin(), arr.end());

    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a;
        key.push_back(a);
    }

    for (int i = 0; i < m; i++) {
        // if (binary_search(arr.begin(), arr.end(), key[i]))
        if (Binary_Search(key[i]))
            cout << 1 << ' ';
        else cout << 0 << ' ';
    }
}

설명

이 문제는 이진 탐색의 개념을 이해하고 구현하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector를 사용하여 구현했습니다. 이진 탐색을 하기 위해선 기본적으로 정렬되어 있어야하며 기준점으로부터 크거나 작거나 따지며 키값을 확인합니다. 키값으로 입력 받은 것을 하나씩 이진 탐색으로 찾고 해당 배열에 있다면 1을 없다면 0을 출력합니다.

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<vector>
-vector<자료형> 변수명; : 배열 자료구조 사용

---

결과