[백준/BOJ] 1920번: 수 찾기 ( 이진 탐색 Binary Search ) - C++ 문제 풀이

 

문제 설명

 

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

 

풀이

이진 탐색을 통해서 찾고자 하는 숫자 X가 주어진 수들 중에 있는지를 판단하는 문제입니다.

 

이진 탐색 ( Binary Search ) 은 전체 구간을 둘로 나누는 과정을, 각 구간의 크기가 0이 될 때까지 반복하면서, 구간 내에 찾는 숫자가 있는지를 검사하는 방법입니다.

 

이진 탐색 ( Binary Search )

알고리즘의 과정은 다음과 같습니다.

1. 전체 구간 G의 중간의 숫자가 찾는 숫자인지 검사한다. 찾는 숫자가 아니면, G구간을 A구간과 B구간으로 나눈다.
2. A구간에 대해 1번의 과정을 반복한다. 이 과정을 나눠진 하위 구간의 크기가 0이 될 때까지 반복한다.
3. A구간에서 찾는 숫자가 없으면, 반대쪽 B구간에 대해서도 A구간과 마찬가지로 탐색한다.

 

이 과정을 코드로 작성하면 다음과 같습니다.

여기서, 배열 A는 문제에서 주어진 값들을 담고 있습니다.

// s ~ e 구간에서 X를 찾는 함수
int bisearch(int X, int s, int e){

    int half = (e + s) / 2;  구간의 중간값을 검사

    if ( A[half] == X )	// X를 찾았음
        return 1;

    if ( s == e )	// 더 이상 구간을 나눌 수 없음. 찾는 값이 없음
        return 0;

    if (bisearch(X, s, half-1))	// 구간을 둘로 나누어 재귀적으로 검사
        return 1;
    
    if (bisearch(X, half+1, e))
        return 1;
            
    return 0;
}

 

이 과정을 좀 더 빠르게 할 수 있는 방법이 있습니다.

배열 A의 값들을 오름차순으로 정렬한다면, 나누어진 두 개의 구간 중 한쪽만 검사해도 충분합니다.

 

정렬에 관한 내용은 여기에 정리해 두었습니다.

[C++] STL sort 함수 사용법

 

만약 중간 값 A [half]보다 X의 값이 작다면, 반대쪽 [ half+1, e ] 구간은 탐색할 필요가 없습니다.

이를 위의 코드에 적용하면 다음과 같습니다.

int bisearch(int X, int s, int e){

    int half = (e + s) / 2;

    if ( A[half] == X )
        return 1;

    if ( s == e )
        return 0;

    // 정렬을 했다면
    // X의 값과 중간 값을 비교해서 한 쪽만 탐색할 수 있다
    
    if ( X < A[half])	
    {
        if (bisearch(X, s, half-1))
            return 1;
    }
    else{
        if (bisearch(X, half+1, e))
            return 1;
    }
        
    return 0;
}

 

이제 코드는 제대로 동작합니다.

그런데, 반드시 재귀 함수를 써야 할까요?

재귀 함수는 같은 함수를 여러 번  호출해야 하기 때문에 일반적으로 비용이 많이 듭니다.

 

이 문제에서는 굳이 재귀 함수를 사용하지 않더라도 해결할 수 있습니다.

int bisearch(int X, int s, int e){

    while( s <= e){	// 구간이 0보다 클 때까지 반복
    
        int half = (e + s) / 2;

        if ( A[half] == X )
            return 1;

        if ( X < A[half])
            e = half-1;
        else
            s = half+1;
    }

    return 0;
}

 

마지막으로, 표준 템플릿 라이브러리( standard template library )를 이용하는 방법도 있습니다.

이때, 배열 A는 정렬되어 있어야 합니다.

#include <algorithm>

int stl_bisearch(int X, int s, int e){

    // 구간의 마지막 원소 대신, 마지막 원소의 다음을 입력한다.
    return std::binary_search( A + s, A + e + 1, X);
}

 

 

소스 코드

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

#define SIZE 100000
typedef long long MTYPE;

MTYPE A[SIZE];

int bisearch(int X, int s, int e){

    while( s <= e){
    
        int half = (e + s) / 2;

        if ( A[half] == X )
            return 1;

        if ( X < A[half])
            e = half-1;
        else
            s = half+1;
    }

    return 0;
}


int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> A[i];
    }

    sort( A, A+N);  // 계산량을 줄이기 위해 정렬

    int M, X;
    cin >> M;

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

        int ret = bisearch(X, 0, N-1);
        cout << ret << "\n";
    }

    return 0;
}