문제
N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요.
💡 입력설명
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다. 두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
💡 출력설명
첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.
💡 입력예제
8 32
23 87 65 12 57 32 99 81
💡 출력예제
3
코드
최종 풀이
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m, i, tmp, lt = 0, rt, mid;
scanf("%d %d", &n, &m);
vector<int> a;
for(i = 0; i < n; i++) {
scanf("%d", &tmp);
a.push_back(tmp);
}
sort(a.begin(), a.end());
rt = n - 1;
while (lt <= rt) {
mid = (lt + rt) / 2;
if(a[mid] == m) {
printf("%d", mid + 1);
break;
} else if(m < a[mid]) {
rt = mid - 1;
} else if(m > a[mid]) {
lt = mid + 1;
}
}
return 0;
}
설명
사용자로부터 N, M을 입력받고 N의 크기를 vector를 a를 선언하고 동적으로 값을 입력받아 할당한다.
오름차순으로 정렬하기 위해 퀵정렬을 이용한다.(sort)
배열의 두 포인트에 해당하는 lt 와 rt를 선언하고 각각 0과 n-1을 할당받는다.
이분탐색 동안 lt, rt가 서로 엇갈리지 않도록 lt가 rt이하 만큼 반복하고 반복하는 동안 중간 point에 해당하는 mid를 lt와 rt합의 2로 나눈 값으로 갱신해나간다.
만약 M값이 중간 값보다 클 경우 중간 지점 이하의 값들은 해당하지 않으므로 lt의 값을 mid + 1로 할당하고 작을 경우 중간 지점 이상의 값들에 해당하지 않으므로 rt를 mid - 1로 할당한다.
마지막으로 같을 경우 중간위치에 + 1한 값(위치번호)을 출력하고 break를 통해 해당 반복문을 탈출한다.
배운 점
이분탐색
개념
정렬된 배열에서 특정 데이터를 찾을 때 탐색 범위를 절반씩 줄여나가면서 찾는 Search 알고리즘이다.
동작원리
1부터 100까지의 데이터 중에서 key가 37인 데이터를 찾는다고 가정할 때 다음과 같이 작동한다.
(1) 1 ~ 100
lt는 1, rt는 100이고 mid는 (1 + 100) / 2인 50이다. (소수점은 포함하지 않는다.)
key값은 mid값보다 작으므로 mid이후에 있는 값들을 해당하지 않는다. 따라서 rt값을 mid - 1로 할당한다.
(2) 1 ~ 49
lt는 1, rt는 49이고 mid는 (1 + 49) / 2인 25이다.
key값은 mid값보다 크므로 mid이전에 있는 값들을 해당하지 않는다. 따라서 lt값을 mid + 1로 할당한다.
(3) 26 ~ 49
lt는 1, rt는 49이고 mid는 (1 + 49) / 2인 25이다.
key값은 mid와 같으므로 mid를 출력한다.
시간복잡도
탐색 대상을 절반씩 줄여나가기 때때문에 10만 개의 데이터가 있다고 가정해도 16번만에 끝낼 수 있다.
따라서 시간복잡도는 O(log n)이다.
vector 동적할당
vector 선언(공간할당X)
vector<int> a;
vector의 끝에 요소 추가
int n, tmp;
vector<int> a;
for(i = 0; i < n; i++) {
scanf("%d", &tmp);
a.push_back(tmp);
}n번 입력한 tmp를 a vector끝에 요소를 할당한다.
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.
