[C++] 백준 알고리즘 1920 수 찾기 (이분 탐색)

1920번: 수 찾기 (acmicpc.net)

1920번: 수 찾기

이분 탐색은 효율성을 요구하는 문제에서 많이 쓰인다고한다.

이러한 이분 탐색은 실생활에서도 많이 쓰인다.

 

최근에 무한도전을 봤는데 노홍철이 생각한 숫자를 멤버들이 특정 횟수 내에 맞춰야하는 게임을 했다.

1~100 까지의 수라고 하면, 50을 물어보고 up down을 해서 범위를 좁혀나가는게 가장 현명하다.

이 방법이 이분 탐색이다.

 

C++에서는 #include<iostream>을 통해 binary_search라는 함수를 사용할 수 있다.

이 경우 원하는 요소가 있으면 1을 반환, 없으면 0을 반환한다.

그런데 보통의 알고리즘 문제에서는 1, 0을 반환하는 것 뿐만 아니라 해당 요소의 인덱스 (위치) 등을 물어볼 수도 있기 때문에 이를 구현할 줄 알아야한다.

---

해당 문제는 함수를 이용해서 풀었다.

주의해야할 점은, 이분 탐색에서는 정렬이 필수라는 점이다.

위에서 게임을 예시로 들었듯이, 50에서 up 이면 50 위 배열에서 찾아야하는데 정렬이 안되어 있으면 어디가 50이라는 숫자의 윗 부분인지 알 수가 없기 때문이다.

---

이를 구현하기 위해서는 left와 right를 설정해야한다. left는 배열의 맨 앞부분이고, right는 배열의 맨 뒷부분이다. 그리고 중간값 mid를 설정한다.

 

• 배열[mid] 값이 (= arr[mid] ) 찾고자 하는 값인지 확인한다. 찾고자 하는 값이면 true를 리턴한다.
• 찾고자 하는 값이 배열[mid] 값 보다 작으면 right = mid - 1 를 해준다. mid는 찾고자 하는 값이 아니므로 빼고, 그 바로 아래의 값을 상한선으로 잡아 그 안에서 탐색하면 된다. (50을 불렀을 때 up이라고 한다면 51~100사이라고 유추하는 것과 같다)
• 찾고자 하는 값이 배열[mid] 값 보다 크면 left = mid + 1을 해주면 된다. (50을 불렀을 때 down이라고 한다면 1~49 사이라고 유추하는 것과 같다.)

그러다가 left>right 가 되는 지점에서 탐색을 멈춘다. 이때까지도 탐색이 안된다면 그 수는 배열에 존재하지 않는 것이다!

 

이분 탐색 연습을 위해.. 다음 번에 이분 탐색 문제를 푼다면 직접 구현해보도록 하겠다

 

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

using namespace std;

int main(){
    //입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0; i<n; i++)
        cin>>arr[i];
    sort(arr.begin(), arr.end()); //이분 탐색은 정렬 필수

    int m, temp;
    cin>>m;
    for(int i=0; i<m; i++){
        cin>>temp;
        cout<<binary_search(arr.begin(), arr.end(), temp)<<'\n';
    }
}