Boj 10815 c++ 숫자카드

알고리즘 공부 기록 시작

오늘 푼 문제의 태그는 자료구조, 정렬, 이분 탐색, 해시를 이용한 집합과 맵이였다.

문제를 들여다보면 상근이가 가지고 있는 숫자카드 N개를 입력받고 , 다음 줄에 또 다시 숫자를 M개 입력 받아 가지고 있는 숫자카드 중에서 있는지 확인하는 문제였다.

가지고 있는 숫자 카드 N개 중에서 있으면, 1을 출력하고 없으면 0을 출력하는 간단한 예제이다. 하지만 N과 M의 범위가 1~500000사이이기 때문에 단순 이중 for 문으로 풀이하다간 시간제한에 걸려 절대 풀지 못한다.

때문에 입력 받은 숫자카드들을 내림차순, 혹은 오름차순으로 정렬한 후 이분 탐색을 통해 참, 거짓을 판별하는 알고리즘을 구현해야 한다.

처음에는 선택 정렬을 이용했지만 시간 복잡도 문제로 라이브러리 정렬함수로 대체하였다.

함수 사용 방식은 벡터(배열)의 처음과 마지막을 입력하는 것이였다. 배열의 크기는 입력 받는 숫자카드의 개수 만큼 할당하였다. N개의 숫자카드는 오름차순으로 정렬되어있었고, 이 이후에는 이분탐색을 이용하여 찾으려는 숫자와 숫자카드의 중앙값을 비교하였다.

M개의 숫자를 입력받을 때 마다 비교하여 0 또는 1을 출력하는 구조였다.

*이분탐색이란?

탐색 범위를 점점 좁혀나가며 데이터를 탐색하는 방식이다.

시간 복잡도가 선형탐색에 비해 훨씬 효율적이며, 동작의 수를 줄일 수 있다.

이분탐색을 위해서는 high(가장 오른쪽 값의 index), low( 가장 왼쪽 값의 index), 그리고 이 둘을 더한 값의 평균인 mid, 총 3개의 변수가 필요하다.

우선 가장 바깥쪽 for 문에서 high, low값을 초기화 해준다. 그리고 mid를 이용하여 중앙값을 탐색하며, 구하려는 값 보다 중앙값이 크거나 작으면 탐색 범위를 절반으로 줄인다.(이때 크거나 작은 중앙값에 1을 빼거나 더하여 high와 low로 바꾼다.)

이때 값을 비교하여 수를 찾으면 while 문을 벗어나지만, 끝까지 못찾는 경우가 발생할 수 있기에 while문 실행 조건을 while(low<=high)로 설정하여 루프를 탈출할 수 있도록 한다.

저장된 값의 참 거짓에 따라 1, 또는 0을 출력하면 완성된다.

wandolph