https://www.acmicpc.net/problem/10815
문제
> 숫자 카드는 정수 하나가 적혀져 있는 카드이다.
> 상근이는 숫자 카드 N개를 가지고 있다.
> 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.접근
이분탐색을 사용해서 찾으려는 수를 상근이가 가진 수들의 인덱스를 통해 탐색한다.
상근이가 가진 수를 오름차순으로 정렬을 먼저하고
최초로 0, 상근이가 가진 카드의 수 -1(인덱스로할거라), 찾으려는 수 이렇게 입력으로 이분탐색을 한다.
이제 탐색이 진행 될 때마다 좌,우값을 갱신시켜 재귀로 범위를 좁혀나가며 최종적으로 수가 존재하지 않을 때 까지 진행한다.
있으면 1, 없으면 0을 출력한다.
문제해결
> main함수에서 입력으로 상근이의 카드 수, 각각의 카드를 받는다.
> 탐색을 위해 오름차순으로 정렬해주고, 찾으려는 카드의 수와 카드를 입력받는다.
> 카드를 입력받으면서 상근이가 가지고있는지 탐색을 위한 이분탐색에 넣어준다.
> 최초로 0, 상근이가 가진 카드수-1, 찾으려는 카드를 넣고 Card함수를 돌린다.
> 재귀의 탈출조건은 범위의 역전, 즉 탐색할 값이 더이상 없어 전의 mid값이 left보다 작아지거나, right보다 커질때 이다. 그리고 찾으려는 카드가 없다는 뜻이므로 0을 반환한다.
> 이분탐색으로 반 나눠서 탐색하므로 중간값 mid를 범위의 중간으로 구해준다.
> mid값을 인덱스로 가지는 상근이가 가진 카드와 찾으려는 카드 num을 비교해 각각의 경우를 따진다.
값이 같다면 찾으려는 카드이므로 1을 반환한다.
> 더 작다면 왼쪽 부분을 탐색하므로 범위를 left, mid-1로 새로 잡고 재귀로 탐색을 이어간다.
> 크다면 mid+1, right로 범위를 잡고 탐색한다.
> 최종적으로 탐색이 끝나면 나온 반환값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<int> card;
int Card(int left, int right, int num)
{
if (left > right) return 0;
int mid = (left + right) / 2;
if (num == card[mid]) return 1;
if (num > card[mid]) return Card(mid + 1, right, num);
if (num < card[mid]) return Card(left, mid - 1, num);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
card.resize(N);
for (int i = 0; i < N; i++) cin >> card[i];
sort(card.begin(), card.end());
cin >> M;
for (int i = 0; i < M; i++)
{
int t;
cin >> t;
cout << Card(0, card.size() - 1, t) << " ";
}
}
후기
이진 탐색의 개념을 다지기 위해 풀어봤다. 재귀를 최근에 몇번 연습해서 구조는 잘 짰는데 Card함수에서 mid를 인덱스로 해줬는데 card[mid]로 안해주는 실수, main에서 sort안해주는 실수 등등이 있었다. 전체적으로 더 구조를 잘 짜보자
