2023-08-07-find-num-1920

• toc {:toc}

  1920: 수 찾기 문제 확인하기

풀이

단순 선형 탐색으로 찾는 방식은 시간복잡도가 높아 풀 수 없다. 다음의 방법으로 이진 탐색을 선택할 수 있다. 아래처럼 재귀적인 방식으로 풀이했다. 하지만 경험상 재귀적인 방식은 반복문을 사용한 방식에 비해 시간복잡도가 더 높게 측정되는 경우가 많다. 일반적으로는 반복문을 사용한 이진 탐색 방식을 사용하자.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
LL N, M;
int res, check = 0, idx = 0;
vector<int> vec;
 
 
int search(vector<int>& v, int num, int s, int e){
    if (s > e) return 0;
 
    int mid = (s + e) / 2;
 
    if (v[mid] == num) return 1;
    else if (v[mid] > num) return search(v, num, s, mid-1);
    else return search(v, num, mid+1, e);
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> N;
    int ins = 0;
    int val;
    for(int i=0; i<N; i++){
        cin >> val;
        vec.push_back(val);
    }
    sort(vec.begin(), vec.end());
 
    cin >> M;
 
    while (M--) {
        res = 0;
        cin >> val;
        res = search(vec, val, 0, vec.size()-1);
        if (res) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
    
 
    return 0;
}