백준 1920 수 찾기 풀이 (Binary Search)
문제
https://www.acmicpc.net/problem/1920
문제내용
N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다.
출력
M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.
예제 입력 1
5
4 1 5 2 3
5
1 3 7 9 5
예제 입력 2
1
1
0
0
1
문제풀이
문제해설
- N개의 정수가 주어졌을 때 어떤 정수 X가 존재하는지 확인하는 문제이다.
- 하지만 문제 조건에서 N과 M의 크기는 최대 100000이기 때문에 이중 for문으로 일일이 확인하면 시간 복잡도가 O(N^2)이 되어서 시간초가가 발생한다
- 따라서 시간 복잡도가 O(logN)인 이진 탐색을 사용한다.
이진 탐색 예시 1
- 1, 2, 3, 4, 5로 정렬된 숫자에서 6이라는 숫자를 찾는다고 가정한다.
- start를 1, end를 5로 하면 middle은 3이 된다.
- 6은 3보다 크기 때문에 오른쪽으로 다시 이진 탐색을 한다.
- start를 4, end를 5로 하면 middle은 4가 된다.
- 6은 4보다 크기 때문에 오른쪽으로 다시 이진 탐색을 한다.
- start를 5, end를 5로 하면 middle은 5가 된다.
- 6은 5보다 크기 때문에 오른쪽으로 다시 이진 탐색을 한다.
- start를 6, end를 5로 하면 start가 end보다 크기 때문에 더 이상 탐색을 할 수 없게 된다.
이진 탐색 예시 2
- 1, 2, 3, 4, 5로 정렬된 숫자에서 0이라는 숫자를 찾는다고 가정한다.
- start를 1, end를 5로 하면 middle은 3이 된다.
- 0은 3보다 작기 때문에 왼쪽으로 다시 이진 탐색을 한다.
- start를 1, end를 2로 하면 middle은 1이 된다.
- 0은 1보다 작기 때문에 왼쪽으로 다시 이진 탐색을 한다.
- start를 1, end를 1로 하면 middle은 1이 된다.
- 0은 1보다 작기 때문에 왼쪽으로 다시 이진 탐색을 한다.
- start를 1 end를 0으로 하면 start가 end보다 크기 때문에 더 이상 탐색을 할 수 없게 된다.
이진 탐색 예시 3
- 1, 2, 3, 4, 5로 정렬된 숫자에서 2라는 숫자를 찾는다고 가정한다.
- start를 1, end를 5로 하면 middle은 3이 된다.
- 2는 3보다 작기 때문에 왼쪽으로 다시 이진 탐색을 한다.
- start는 1, end를 2로 하면 middle은 1이 된다.
- 2는 1보다 크기 때문에 오른쪽으로 다시 이진 탐색을 한다.
- start는 2, end를 2로 하면 middle은 2가 된다.
- 목표하던 값을 찾게 된다.
코드 설명1
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int N; // 주어진 수의 개수
int M; // 탐색할 수의 개수
vector<int> v; // 주어진 수의 배열
int m[100001]; // 탐색할 수의 배열
int result = 0; // 결과값
- 필요한 헤더를 추가하고, 변수를 선언한다.
- sort 함수를 사용하기 위해 algorithm 헤더를 추가한다.
코드 설명2
void f(int input, int start, int end) {
int middle = (start + end) / 2;
// 탐색할 값이 존재한다면 결과값에 1을 넣고 리턴
if (v[middle] == input) {
result = 1;
return;
}
// 더이상 찾을 수 없을 때 결과값에 0을 넣고 리턴
if (middle > end || middle < start) {
result = 0;
return;
}
// 입력값이 크면 오른쪽, 작으면 왼쪽 탐색
if (v[middle]<input) {
return f(input, middle+1, end);
}
else if(v[middle] > input) {
return f(input, 0, middle-1);
}
}
- 배열의 start와 end의 middle을 구한다.
- 배열의 middle에 있는 값과 input을 비교한다.
- 값이 같으면 1를 반환하고 리턴한다.
- input이 더 크면 오른쪽 탐색을 힌디.
- middle+1 을 start으로 재귀 호출한다.
- input이 더 작으면 왼쪽 탐색을 한다.
- middle-1을 end으로 하고 재귀 호춣한다.
코드 설명3
int main() {
// 데이터 입력
cin >> N;
for (int i = 1; i <= N; i++) {
int a;
cin >> a;
v.push_back(a);
}
cin >> M;
for (int i = 1; i <= M; i++) { cin >> m[i];}
// 정렬
sort(v.begin(), v.end());
// 탐색
for (int i = 1; i <= M; i++) {
result = 0; // 0으로 초기화
f(m[i], 0, N-1);
cout << result<<"\n";
}
return 0;
}
- 문제에서 필요한 입력을 수행한다.
- 이진 탐색을 하기 위해서는 정렬되어 있어야 하기 sort함수를 사용해서 정렬한다.
- 이진 탐색을 하면서 값을 출력한다.
전체코드
/*
아이디어
- 배열로 A에 해당하는 정수를 입력
- 배열로 A에 탐색할 정수를 입력
- A 탐색할 정수 갯수 만큼 반복해서 결과값 출력
- 배열 A에 중간값을 구한다.
- 입력 정수보다 크면 오른쪽, 작으면 왼쪽으로 재귀 호출
- 찾는 수가 나오면 해당 숫자에 1를 반영
- 찾는 수가 나오지 않으면 숫자에 0을 반영
자료구조
- int 형 배열 A, 배열 M, 결과값
*/
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int N; // 주어진 수의 개수
int M; // 탐색할 수의 개수
vector<int> v; // 주어진 수의 배열
int m[100001]; // 탐색할 수의 배열
int result = 0; // 결과값
// 탐색할 함수
void f(int input, int start, int end) {
int middle = (start + end) / 2;
// 탐색할 값이 존재한다면 결과값에 1을 넣고 리턴
if (v[middle] == input) {
result = 1;
return;
}
// 더이상 찾을 수 없을 때 결과값에 0을 넣고 리턴
if (middle > end || middle < start) {
result = 0;
return;
}
// 입력값이 크면 오른쪽, 작으면 왼쪽 탐색
if (v[middle]<input) {
return f(input, middle+1, end);
}
else if(v[middle] > input) {
return f(input, 0, middle-1);
}
}
int main() {
// 데이터 입력
cin >> N;
for (int i = 1; i <= N; i++) {
int a;
cin >> a;
v.push_back(a);
}
cin >> M;
for (int i = 1; i <= M; i++) { cin >> m[i];}
// 정렬
sort(v.begin(), v.end());
// 탐색
for (int i = 1; i <= M; i++) {
result = 0; // 0으로 초기화
f(m[i], 0, N-1);
cout << result<<"\n";
}
return 0;
}
다른 방식 풀이 방법(배열과 while문 활용)
#include <iostream>
#include <algorithm>
using namespace std;
int N; // 주어진 수의 갯수
int M; // 탐색할 수의 갯수
int a[100001]; // 주어진 수의 배열
int m[100001]; // 탐색할 수의 갯수
void f(int input) {
int start = 1;
int end = N;
while (start <= end) {
int middle = (start + end) / 2;
if (a[middle] == input) {
cout << 1 << "\n";
return;
}
if (a[middle] < input)
start = middle + 1;
else
end = middle - 1;
}
cout << 0 << "\n";
}
int main() {
cin >> N;
for (int i = 1; i <= N; i++)
cin >> a[i];
cin >> M;
for (int i = 1; i <= M; i++)
cin >> m[i];
sort(a+1, a + (N+1));
for (int i = 1; i <= M; i++)
f(m[i]);
return 0;
}