백준 1920번 수 찾기

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

자료구조 시간에 많이 다루던 이분 탐색, 혹은 이진 탐색 문제였습니다.

네이버 사전에서는 이진 탐색이 올바른 표현인데 백준에서는 이분 탐색으로 표현을 하므로 논란이 생기지 않도록 BinarySearch라고 하겠습니다.

BinarySearch는 배열 내 숫자가 정렬되어야 올바르게 탐색을 할 수 있습니다.

처음부터 끝까지 모두 확인하며 탐색하는 방법은 시간복잡도가 O(N)이지만 BinarySearch는 시간복잡도가 O(logN)이기 때문에 웬만하면 BinarySearch를 통해 탐색하는 것이 효율적입니다.

C++에서는 algorithm 헤더파일에 sort 함수를 제공하기 때문에 쉽게 정렬을 할 수 있습니다.

그리고 주의할 점은, cin의 속도 향상을 위해 ios_base::sync_with_stdio(0);cin.tie(0); 를 추가해주고 개행할 때 endl 대신 "\n"를 써줘야한다는 점입니다.

위와 같이 코드를 작성하지 않으면 시간초과가 발생하는 불상사가 발생합니다...

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 100000;

 

int N, M;

vector<int> A;

 

int binarySearch(int low, int high, int target)

{

        //기저 사례: low가 high보다 크면 없는 수

        if (low > high)

                 return 0;

        else

        {

                 int mid = (low + high) / 2;

                 //해당 지점에 target이 있다면 찾았으므로 1 반환

                 if (A[mid] == target)

                         return 1;

                 //해당 지점에 있는 수가 target보다 크면 왼쪽 반 탐색

                 else if (A[mid] > target)

                         return binarySearch(low, mid - 1, target);

                 //해당 지점에 있는 수가 target보다 작으면 오른쪽 반 탐색

                 else

                         return binarySearch(mid + 1, high, target);

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상 위해

        cin >> N;

 

        for (int i = 0; i < N; i++)

        {

                 int num;

                 cin >> num;

                 A.push_back(num);

        }

        sort(A.begin(), A.end()); //이분탐색은 정렬되어 있어야한다.

 

        cin >> M;

        for (int i = 0; i < M; i++)

        {

                 int num;

                 cin >> num;

                 cout << binarySearch(0, N - 1, num) << "\n"; //endl 쓰면 시간 초과

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~