[백준] 10815번 숫자 카드

March 20, 2021 ( last updated : March 20, 2021 )
이분탐색 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

[백준] 10815번 숫자 카드

[백준] 10815번 숫자 카드

백준 10815번

간단한 이분 탐색 문제이다. 이분 탐색은 일반적으로 그냥 for문을 이용하여 배열의 모든 요소를 탐색하는 것보다 빠르게 원하는 요소를 찾아낼 수 있다.

먼저 어떤 원리로 더 빠르게 요소를 찾아낼 수 있는지 간단한 예제를 통해서 파악해보도록 하자.

arr = [1,2,3,4,5,6,7]
위와 같은 정렬 된 배열이 있다고 하자.
우리가 찾고 싶은 수는 5 라고 하였을 때 이분탐색으로 어떻게 찾을 수 있을 지 보겠다.

먼저 최소 값과 최대 값을 정한다. 이 경우 최소 값은 1이고 최대 값은 7이다. 그리고 이 둘의 중간 값을 4를 정한다.
처음에 중간 값이 우리가 찾는 타겟 값 5인지 확인한다. 하지만 4와 5는 다르다. 그렇다면 둘을 비교하여서 중간 값이 더 작거나 큰지 확인한다. 이 경우 더 작기 때문에 최솟 값을 중간 값으로 바꿔 준다.

최솟 값: 1 -> 4

이렇게 바꿔주는 이유는 간단하다. 정렬된 상태이기 때문에 4보다 작은 값에는 타겟 값이 없다는 것을 알 수 있기 때문이다.
이후 4와 7 사이의 값 5를 중간 값으로 다시 정해주고 타겟 값과 비교하면 바로 타겟 값을 구할 수 있다.

우리는 이분 탐색을 통해서 6까지 6번의 탐색이 필요했을 것을 2번만에 찾을 수 있었다. 이처럼 이분 탐색은 일반적인 탐색보다 짧은 시간이 걸리기 때문에 어떠한 타겟 값을 정렬 된 숫자 안에서 찾을 때 많이 쓰인다.

그렇다면 이러한 이분 탐색을 해당 문제에 적용한 결과를 보자.

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

int main() {
    int N, M;
    cin >> N;
    int card[N];
    bool flag=false;

    for(int i=0; i<N; i++){
        cin >> card[i];
    }
    sort(card, card + N);
    cin >> M;
    int shot[M];
    for(int i=0; i<M; i++){
        cin >> shot[i];
    }

    for(int i=0; i<M; i++){
        flag = false;
        int start =0, end = N-1;
        int mid = (end-start)/2;
        while(end-start >=0){
            if(card[mid] == shot[i]){
                shot[i] = 1;
                flag = true;
                break;
            } else if (card[mid] <= shot[i]){
                start = mid + 1;
            } else {
                end = mid -1;
            }
            mid = (end+start)/2;
        }
        if(!flag){
            shot[i] = 0;
        }
    }

    for (int i=0; i<M; i++){
        cout << shot[i] << " ";
    }
    cout << endl;
    return 0;
}

Originally published March 20, 2021
Latest update March 20, 2021

Related posts :

{# #}