[ C++ ] 백준 1920: 수 찾기

 

 

안녕하세요? 수구리입니다.

이번에 풀어볼 문제는 이분 탐색입니다.

이분 탐색은 한 배열에서 특정 요소를 찾기 위해서 사용되는 방법입니다.

이는 제가 요즘 즐겨보고 있는 터퀴즈에서 쉽게 접할 수 있습니다!

터퀴즈의 마지막 부분에서 퀴즈를 내는 부분에서 이용진 님께서

"~~ 산의 높이는 몇 m일까요?" 라던지 " ~~ 의 키는 몇 cm일까요?" 등의 문제를 낸 기억이 있습니다.

여기서 게스트는 1도 모르기 때문에 특정 숫자를 말하죠.

그러면 이용진 님께서는 답이 게스트가 말한 값보다 크다면 UP을,

아니라면 DOWN을 말하시죠! 이게 바로 이분 탐색 방법이라고 볼 수 있습니다.

생각보다 일상생활에서 흔히 볼 수 있죠??

아무튼 각설하고 바로 문제 확인해 보시기 바랍니다!

 

 

 

[ 문제 ] 1920: 수 찾기

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

 

 

[ 나의 풀이 ]

 

// date : 2021.11.24
// problom : 1920
// title : 수 찾기
// description : 배열의 요소를 이분탐색으로 찾아보자!

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

using namespace std;

int N,M;
vector<int> A;

void findElementInA(int target){
    int start = 0;
    int end = A.size();

    // find target in A
    while(end >= start){
        int mid = (start+end) / 2;
        if (A[mid] == target){
            cout << "1\n";
            return;
        } else if (A[mid] < target) {
            start = mid + 1;
        } else if (A[mid] > target) {
            end = mid - 1;
        }
    }
    
    cout << "0\n";
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int x;
   
    cin >> N;
    for(int i=0; i<N; i++){
       cin >> x;
       A.push_back(x);
    }
    sort(A.begin(), A.end());
    
    cin >> M;
    for(int i=0; i<M; i++){
       cin >> x;
       findElementInA(x);
    }
}

 

 

 

[ 설명 ]

1. 배열 A의 크기와 A의 요소들을 크기만큼 입력받는다.

2. 이분 탐색을 하기 위해서 정렬!! (★ 필수 ★)

3. 배열 B의 크기와 B의 요소를 하나씩 입력 받음과 동시에 입력받은 요소(x)를 가지고 findElementInA (x)를 호출한다.

4. findElementInA 함수 내부에서는 시작(start)과 끝(end)을 정하고, while 종료 조건으로 end >= start 인 경우만 반복

5. 위에서 구한 start와 end 값을 가지고 mid index 값을 구하고, 가장 먼저 mid index에 접근해 target이 맞는지 확인한다. 맞다면 target을 찾은 경우이므로 1을 출력하고 빠져나온다.

6. 만약 찾고자 하는 값(target)이 A [mid] 값 (즉, 초기에는 A의 중간값이다.) 보다 크다면 오른쪽에 target이 있기 때문에 왼쪽 절반은 탐색하지 않게 하기 위해서 start의 값을 mid + 1로 변경.

7. 반대의 경우는 설명 생략!

8. end 값이 start보다 작아지면 종료한다.

9. while 문을 빠져나온다면 target을 찾지 못한 경우이므로 0을 출력한다.