[BOJ 1920] 백준 수 찾기 풀이 - C++

사용언어 :  C++

 

 

 

문제풀이

* binary search(이진탐색) 사용

 

- 전역변수

int N, M; int tmp;
int A[100000];

 

-main함수

int main() {

	ios::sync_with_stdio(false); 
	cin.tie(0);
    // 위에 두개 작성해야 시간초과 안난다 
    
    //N만큼 A배열에 값 저장하기
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
    
    //이진탐색을 사용하기 위해 오름차순으로 정렬
	sort(A, A + N);

	//M만큼 값 존재유무 확인하기
	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		cout << binarysearch(tmp) << "\n";
	}
}

 

-binary search 함수 (이진탐색을 통해 배열에 해당 값이 있는지 확인한다)

int binarysearch(int x) {
	
    //초기 start, end 값 설정
	int start = 0;
	int end = N - 1;
    
    //start가 end보다 작거나 같을 때까지만 진행
    //while 끝까지 돌게되면 해당 값이 없는 것 -> return 0 
	while (start <= end) {
		int center = (start + end) / 2;
		if (x == A[center]) //해당 값 찾았을 때
			return 1;
		else if (x > A[center]) //해당 값이 중간 값보다 클 때
			start = center + 1;
		else  //해당 값이 중간 값보다 작을 때
			end = center - 1;
	}
	return 0; //while 빠져나갔으면 0 리턴
}

start, end, center는 A배열의 index에 들어갈 값이다. 

 

 

전체코드

#include <iostream>
#include<algorithm>
using namespace std;
int N, M; int tmp;
int A[100000];

int binarysearch(int x) {
	int start = 0;
	int end = N - 1;
	while (start <= end) {
		int center = (start + end) / 2;
		if (x == A[center])
			return 1;
		else if (x > A[center])
			start = center + 1;
		else 
			end = center - 1;
	}
	return 0;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
    
	sort(A, A + N);

	cin >> M;
	for (int i = 0; i < M; i++) {
		cin >> tmp;
		cout << binarysearch(tmp) << "\n";
	}
}

 

 

---

총평

이진탐색 기본문제. 이진탐색은 다른 알고리즘에 비해 몇 번 접한 적이 있어서 나름 수월하게 풀었다.

ios::sync_with_stdio(false);
	cin.tie(0);

잊지말고 꼭 작성하자!!

---

문제 출처

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

1920번: 수 찾기