본문 바로가기
<알고리즘 문제풀이&연습>/[C++] 백준

[백준 1920] 수 찾기 (이진탐색)

by 사용자 BlockDMask 2017. 10. 8.
반응형
  • 안녕하세요. BlockDMask 입니다. 

  • 오늘은 '수 찾기' 라는 문제를 풀어보았습니다.

  • 음..은근히 생각을 하게 하는 문제였습니다.
    '시간초과' 때문에;; ㅎㅎ
    170906 문제 빼먹음 -> 171008 완료

0. 제목

  • 백준 1920 수 찾기 (이진탐색)

  • BOJ 1920 수 찾기 (Binary Search)

1. 문제설명


N개의 정수 A[1], A[2], A[3], A[4], ..., A[N-2], A[N-1], A[N] 이 주어져 있을 때, 


이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 구현하면 됩니다.


입력 --


첫째 줄에 자연수 N(1<= N <=100,000) 이 주어집니다.


둘째 줄에는 N개의 정수 A[1], A[2], A[3], A[4], ..., A[N-2], A[N-1], A[N] 이 주어집니다.


셋째 줄에는 M (1<= M <= 100,000) 이 주어집니다.


마지막 줄에는 M 개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 됩니다.


출력 --


M개의 줄에 답을 출력하면 됩니다.


존재하면 1 출력.

존재하지 않으면 0 출력.


2. 풀이과정


Linear Search(선형탐색)을 이용하여 문제를 풀었는데 '시간초과'가 나왔습니다.


좀더 좋은 방법이 없을까 고민 끝에, 


받은 배열을 Quick Sort로 렬을 한 후


Binary Search(이진탐색)을 이용하여 문제를 풀었습니다.



이진탐색을 구현하는 방법이 세가지 있습니다


a) 직접 구현 - 반복문을 이용한 이진 탐색


b) 직접 구현 - 재귀를 이용한 이진 탐색


c) STL 이용 - binary_search 함수 이용한 이진탐색


세가지 방법의 이진탐색의 코드는

[바로가기]에 정리해 두었습니다. (준비중..)


3. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//https://www.acmicpc.net/problem/1920
//BOJ_1920_수찾기
 
#include<iostream>
#include<cstdio>
#include<algorithm>
 
using namespace std;
 
int arr[100001];
 
//이진탐색(Binary Search)을 이용하여 탐색
void Solution(int n, int key){
 
    int start = 0;
    int end = n-1;
    int mid;
 
    while(end - start >= 0){
        mid = (start + end)/2;
 
        if(arr[mid] == key){   //key 값이 배열의 중앙 값과 같을때
            printf("1\n");
            return ;
 
        }else if(arr[mid] > key) { //key 값이 배열의 중앙 값보다 작을때 (왼쪽으로)
            end = mid - 1;
 
        }else{  //key 값이 배열의 중앙 값보다 클때 (오른쪽으로)
            start = mid + 1;
        }
    }
 
    printf("0\n");
    return ;
}
 
int main(void){
 
    int n, m, tmp;
 
    //입력
    scanf("%d"&n);
 
    for(int i=0; i<n; i++){
        scanf("%d"&arr[i]);
    }
    sort(arr, arr+n);   //quick sort를 이용해 배열 오름차순으로 정렬
 
    //입력
    scanf("%d"&m);
 
    for(int i=0; i<m; i++){
        scanf("%d"&tmp);
        Solution(n, tmp);
    }
 
    return 0;
}
cs


4. 인증


문제 출처 - https://www.acmicpc.net/problem/1920

감사합니다.트 꾹 부탁드립니다.

반응형

댓글0