백준 알고리즘 1920번 : 수 찾기 (C++)

 

이번 알고리즘 문제는 이진 탐색을 배울 수 있었다.

문제를 처음보고 내가 입력했던 방식은 이중 for문을 통해 찾는 것이었는데, 출력 값이 동일했음에도 시간 제한에 걸려 통과하지 못했다.

그래서 이것저것 검색해본 결과, 이진 탐색 기법을 이용해야 통과할 수 있다고 하였다.

 

이진 탐색은 이분 탐색이라고 불리기도 하는데, 연속된 값 중 정가운데 값을 뽑아

그 값보다 큰지, 작은지를 비교하여 탐색하는 기법이다.

 

출처 : https://medium.com/@codingfreak/binary-search-practice-problems-4c856cd9f26c

투박한 이미지이지만, 전체를 2등분해 찾는 방법을 가장 쉽게 표현한 이미지 같아 첨부하였다.

 

 

#include<iostream>
#include<algorithm>
using namespace std;
 
void BinarySearch(int *arr, int start, int end, int searchNum){
     // 반복문을 통한 이진 탐색 
    int mid;
    
    while(end - start >= 0){
        mid = (start+end)/2;
        
        if(arr[mid] == searchNum){
            printf("1 \n");
            return;
        }else if(arr[mid] > searchNum){
            end = mid - 1;
        }else { // arr[mid] < searchNum
            start = mid + 1;
        }
    }
    
    printf("0 \n");
    return;
    
}
 
/*
void BinarySearch(int *arr, int start, int end, int searchNum){
    // 재귀를 통한 이진 탐색
    int mid;
    
    if(start > end){
        printf("0 \n");
        return;
    }else{
        
        mid = (start+end) / 2;
        
        if(arr[mid] > searchNum){
            return BinarySearch(arr, start, mid - 1, searchNum);
        }else if(arr[mid] < searchNum){
            return BinarySearch(arr, mid + 1, end, searchNum);
        }else{
            printf("1 \n");
            return;
        }
        
    }
    
}
*/
 
int main() {
    
    // https://www.acmicpc.net/problem/1920
    
    int n,m;
    scanf("%d", &n);
    
    int nArr[n];
    
    for(int i=0; i<n; i++)
        scanf("%d", &nArr[i]);
        
    sort(nArr, nArr + n ); 
 // sort 함수를 이용해 오름차순 정렬. sort(배열의 시작점 '주소', 배열의 마지막점 '주소');
    
    scanf("%d", &m);
    
    int tmp;
    int end = sizeof(nArr)/sizeof(nArr[0]);
        
    for(int i=0; i<m; i++){
        scanf("%d",&tmp);
        BinarySearch(nArr, 0, end, tmp);
    }
}

 

C++ 에서 이진 탐색을 구현하는 방법에는 직접 구현하는 방법과 C++ STL의 binary_search 함수를 이용하는 방법이 있다.

나는 이진 탐색의 기본이 없기 때문에, 검색하여 직접 구현하는 방법을 찾아 사용하였다.

사실상 보고 치는거나 다름없다. 그래도 찬찬히 배워서 정리해두는게 좋을 것 같다.

 

참고 - 

개발자 지망생님 블로그 : 
https://blockdmask.tistory.com/166
https://blockdmask.tistory.com/167