[백준(BOJ)] 1920번 : 수 찾기 - C++[CPP]

www.acmicpc.net/problem/1920

1920번: 수 찾기

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 이분 탐색

 

---

 

⊙ 문제 접근 과정

 

문제를 보고 이진 탐색으로 접근해야겠다고 생각했다.

순차 탐색으로 문제를 접근하면 시간 복잡도가 O(N)이다.

그렇지만 이진탐색으로 접근한다면 시간 복잡도를 O(logN)으로 줄일 수 있다.

 

이진 탐색을 STL 라이브러리를 이용하지 않고 직접 구현하여 문제를 풀어봤다.

 

 

---

 

⊙ 문제 풀이

 

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

using namespace std;

int binarySearch(vector<int>& basic,int target, int start, int end) {
    while (start <= end) {
        int mid = (start + end) / 2;

        if(basic[mid]==target)
            return mid;
        else if(basic[mid] > target)
            end = mid - 1;
        else
            start = mid + 1;
    }
    return -1;
}

int N,M;

vector<int> A;
vector<int> target;

int main() {
    cin >> N;

    for (auto i = 0; i < N; i++)
    {
        int x;
        cin>>x;
        A.push_back(x);
    }
    
    sort(A.begin(),A.end());

    cin>> M;

    for (auto i = 0; i< M; i++) {
        int x;
        cin >> x;
        target.push_back(x);
    }

    for(auto i =0; i<M; i++) {
        int result = binarySearch(A,target[i],0,N-1);

        if(result!=-1) {
            cout << "1\n";
        } else cout <<"0\n";
    }
}

 

---

⊙ 결과

 

 

---

⊙ 마무리

 

 

이진 탐색에 대해 정리하고 글을 작성할 예정이다.

 

좋아요는 로그인하지 않아도 누를 수 있습니다!