안녕하세요! 오늘은 BOJ 1920 - 수 찾기 문제를 풀어볼게요.
1. 접근 - 선형 탐색
문제를 읽어보면, N개의 정수 배열 A[N]이 주어지고 나서, M개의 수가 A 배열 안에 있는지 찾아야 해요.
이때 숫자를 배열에서 앞에서부터 하나씩 찾는다고 생각해볼게요.
문제의 예시 입력대로, N = 5, A[5] = {4, 1, 5, 2, 3}이고, M = 5, 즉, 5개의 숫자 1, 3, 7, 9, 5를 차례로 A 배열에서 찾을 거예요.
앞에서부터 순차적으로 찾는다고 생각해 보면, 배열의 앞쪽에 위치한 1을 찾을 때에는 A[1]에 값이 있으니 금방 찾을 수 있지만, 배열의 끝에 있는 4를 찾을 때에는 A[4]에 값이 있으니 배열의 끝까지 탐색해보아야 해요.
존재하지 않는 수를 찾을 때에도 배열을 처음부터 끝까지 전부 살펴봐야 한다는 것을 알 수 있어요.
그래서 한 번 수를 찾을 때마다, 최악의 경우 배열의 원소 N개를 전부 살펴보아야 하니, 시간복잡도는 O(N)이에요.
그런데 이 문제에서는 M개의 수를 찾아야 하니, O(N*M)의 시간복잡도겠네요.
따라서 최악의 경우 N이 100,000이고, M이 100,000일 경우 100억... 정도니까 1초에 10억 번 정도 연산이 진행된다고 가정해도, 제한 시간 내에 찾을 수가 없어요.
이러한 탐색 방식을 선형 탐색(Linear Search)이라고도 불러요.
선형 탐색으로는 이 문제를 해결하기 힘들어 보이니, 다른 방법을 사용해야 할 것 같네요.
2. 접근 - 이분 탐색
시험을 보고 나서, 시험 점수를 친구한테 물어봤더니 바로 알려주지 않고 "업다운"으로 알려준다고 할 때를 생각해 볼게요.
상황을 간단하게 해서, 한 문제당 10점 배점으로 10문제짜리 시험을 본다고 하면 점수는 0, 10, 20, 30, ..., 100점 중 하나일 거예요.
그렇다면, "50점 업? 다운?"을 물어보고, 만약 50점 업이라면 가능한 범위가 60~100점으로 줄었으니, "80점 업? 다운?" - 이런 식으로 몇 번의 질문을 더 해보면서 범위를 좁혀나가다가 시험 점수를 찾을 수 있겠죠?
이러한 아이디어를 가지는 탐색 알고리즘을 알아볼게요.
앞의 상황을 문제의 상황처럼 표현해 보면, N = 11이고, A[11] = {0, 10, 20, 30, 40, ..., 100}과 같은 배열에서 60을 찾아볼게요.
변수 start는 탐색 범위의 가장 왼쪽 인덱스, 변수 end는 탐색 범위의 가장 오른쪽 인덱스로 정의 할게요.
우선 배열의 시작점이 A[0]이므로 인덱스인 0을 start 변수로 잡고, A[10]이 마지막 원소이니 인덱스인 10을 end 변수로 잡을게요.
그리고 mid 변수는 (start + end) / 2로 시작점과 끝점의 인덱스의 절반으로 잡아요.
그러면 mid는 배열의 정가운데 원소의 인덱스가 될 테니, A[mid]는 배열의 정가운데 원소예요.
그리고 A[mid]와 목표로 하는 target = 60을 비교해요.
그런데 정가운데 값보다 target이 더 크니까, 이제 50점 이하의 수들은 신경 쓸 필요가 없어요.
그러니 start를 mid + 1로 만들어줘요.
이제 우리의 탐색 범위는 60점~100점, 인덱스로 보면 6~10으로 좁혀졌어요.
start = 6, end = 10이니, mid = (6 + 10) / 2 = 8이 정가운데 인덱스가 되겠네요.
A[mid] = A[8] = 80이고, target = 60이니 A[mid]의 값이 찾고자 하는 값보다 커요.
그러니 end = mid - 1을 해줘요. 이제 우리의 탐색 범위는 60~70점, 인덱스로 보면 6~7로 좁혀졌어요.
start = 6, end = 7이니, mid = (6 + 7) / 2 = 6.5인데, C++에서 정수끼리 나눗셈을 하면 소수점은 버리니 6이 정가운데 인덱스가 되겠네요.
A[mid] = A[6] = 60이고, target = 60이니 A[mid]의 값이 찾고자 하는 값이니 탐색이 완료되었어요.
어떤가요? 탐색 방식이 이해가 조금 되시나요?
이러한 탐색 알고리즘을 이분 탐색(Binary Search)이라고 해요.
한 번 시행할 때마다, 탐색 범위를 절반으로 줄여나가면서 탐색하기 때문에, 시간 복잡도는 O(logN)이에요. (보통 시간 복잡도를 표기할 때 log의 밑 2를 생략해요.)
잘 생각해 보면 탐색 범위 N이 커지면 커질수록 앞서 살펴본 선형 탐색보다 월등히 빠르다는 것을 알 수 있는데, 0~10000 사이의 값을 찾을 때 0, 1, 2, 3, ...으로 찾으면 정말 답답하겠죠?
그렇다면 만약 배열에 찾으려는 target이 없을 경우는 어떻게 될까요?
이번에는 배열에 없는 수를 찾아야 하니, target = 55라고 가정을 해볼게요.
1, 2단계 시행 과정은 앞에서와 동일한 과정을 거쳐요.
3단계에서, A[mid] = A[6] = 60이 target = 55보다 크니, end = mid - 1로 범위를 줄이려 하겠죠?
그런데 end = 5가 되고, start = 6이 되면서 end와 start의 순서가 역전되었어요.
분명 end는 탐색 범위의 가장 오른쪽 인덱스, 변수 start는 탐색 범위의 가장 왼쪽 인덱스로 정의했으니 순서가 바뀌었다는 뜻은 결국 찾고자 하는 값이 배열에 없었다는 뜻이 돼요.
그러니 end < start와 같은 상황이 되면, 탐색을 마치고 false를 반환하면 되겠네요.
이분탐색을 코드로 직접 구현하면 다음과 같아요.
bool binarySearch(int target) { // 이분탐색
int st = 0;
int ed = n-1;
while (st <= ed) {
int mid = (st + ed) / 2;
if (a[mid] < target) st = mid + 1;
else if (a[mid] == target) return true; // 수가 존재하는 경우
else ed = mid - 1; // a[mid] > target
}
return false; // 수가 존재하지 않는 경우
}
target을 찾을 것이고, 처음 st의 값은 0, ed의 초기값은 n-1이에요. st <= ed인 동안 탐색을 반복할 건데, a[mid]와 target이 같으면 수를 찾은 것이니 true를 반환해요.
st > ed가 되는 경우 수가 존재하지 않으므로 false를 반환할 거예요.
이분 탐색에서 주의할 점이 있어요.
어느 정도 눈썰미가 있으시다면 벌써 알아차리셨겠지만, 배열이 반드시 정렬된 상태여야 사용할 수 있어요.
A[mid] = 50이고 target = 60일 때, 배열에서 A[mid] 이전의 수는 모두 50 이하인 상태여야 start = mid + 1을 해서 좁혀나갈 수 있을 거예요.
만약 정렬이 되지 않았다면 A[mid] 앞에도 찾으려는 값 60이 있을 수 있으니 이분 탐색으로 탐색했을 때, 실제로는 있는 값인데도 없다고 할 수도 있게 되니 사용할 수 없어요.
그렇다면 이 문제에서 N개의 배열을 정렬(O(NlogN))한 후, 이분 탐색(O(log N)) M번을 해야 하니, 시간복잡도는 O(NlogN + MlogN)이 되겠네요.
3. 구현, STL
#include <iostream>
#include <algorithm>
using namespace std;
int a[100001];
int n, m;
bool binarySearch(int target) { // 이분탐색
int st = 0;
int ed = n-1;
while (st <= ed) {
int mid = (st + ed) / 2;
if (a[mid] < target) st = mid + 1;
else if (a[mid] == target) return true; // 수가 존재하는 경우
else ed = mid - 1; // a[mid] > target
}
return false; // 수가 존재하지 않는 경우
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n); // 이분 탐색을 위해 오름차순 정렬
cin >> m;
while (m--) {
int target;
cin >> target;
cout << binarySearch(target) << '\n';
}
return 0;
}
구현은 정직하게 이분 탐색을 하면 되는 문제라서, 크게 어렵지 않을 것 같아요.
이분 탐색 부분은 앞에서 살펴본 것과 같고, 이분 탐색 하기 전에 반드시 정렬을 우선 해야 한다는 것을 잊지 말아 주세요.
#include <iostream>
#include <algorithm>
using namespace std;
int a[100001];
int n, m;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n); // 이분 탐색을 위해 오름차순 정렬
cin >> m;
while (m--) {
int target;
cin >> target;
cout << binary_search(a, a+n, target) << '\n';
}
return 0;
}
STL을 사용해서도 구현할 수 있어요.
binary_search(a, a + n, target)을 해주면, a[0]부터 a[n - 1]까지 이분 탐색으로 target의 값이 존재하면 true, 존재하지 않으면 false를 O(log N)에 반환해요.
