Intro
학부시절에 여러가지 문제들을 겪어 보았지만, 특정한 조건에 만족하는 값을 찾으라는 문제를 겪게 된다면 아무것도 모를 땐 그저 for문을 돌렸던 기억이 난다.
물론 이게 틀린 방법이 아니기는 하다. 데이터가 적을 때는 크게 상관이 없지만 데이터가 많을 때는 어떻게 해야 할까?
https://www.acmicpc.net/problem/2805 (BOJ-나무자르기)
예를들면 이런 상황말이다. 데이터의 입력 범위가 2,000,000,000까지다. 가능한 모든 경우의 수를 그저 for문으로 찾아내려면 얼마나 많은 연산을 해야 할까?
그냥 처음부터 끝까지 뒤져보는 방법을 선형 탐색이라고 한다. 데이터가 적은 경우에는 상관이 없지만 이런 상황에서는 O(n)이라고 해도 적지 않은 데이터를 뒤져봐야 한다. 값을 찾는 것도 찾는 것지만 맞는 조건인 지 체크하는 데 엄청난 시간이 들어갈 수도 있다. 위의 문제에서는 최대 1,000,000개의 나무를 비교해보아야 한다. 즉 2,000,000,000 X 1,000,000번의 연산을 해야 할 수도 있다는 것이다.
이 문제만 예를 들어봐도 그렇다. 값을 찾는것도 문제지만 그 값이 적절한 지 계산하는 것 또한 오래걸린다. 후자 같은 경우는 어떻게 시간을 줄이기가 쉽지 않다. 그렇지만 애초에 탐색하는 시간 자체를 줄여버린다면 어떨까? 휠씬 프로그램이 효율적으로 변할 수 있지 않을까?
이번 포스팅에서는 이분탐색(Binary Search)에 대하여 다루도록 하겠다.
Binary Search
선형 탐색과는 다르게 이분 탐색은 모든 데이터를 하나 하나 뒤져보지 않는다. 찾고자 하는 데이터가 속한 영역을 반으로 나누어, 그 중간 값이 찾고자 하는 데이터보다 크거나 작은가에 따라 탐색하고자 하는 범위를 변경시키는 게 아이디어다. 단, 이러한 알고리즘을 활용하기 전에 선수 조건은 찾고자 하는 데이터들이 정렬 되어 있어야 한다는 것이다. 선형 탐색의 과정은 다음과 같다.
- 찾고자 하는 데이터 영역을 정렬한다.
- 가장 작은 데이터와 가장 큰 데이터를 구해 각 변수에 저장한다. 그 변수값들을 통해 중간 값을 구한다.
- 그 중간값이 찾고자 하는 데이터보다 크다면 가장 큰 데이터를 저장한 변수 값을 그 중간 값 - 1로 갱신한다. 만약 중간값이 찾고자 하는 데이터보다 작다면 가장 작은 데이터를 저장한 변수 값을 그 중간 값 + 1로 갱신한다. 만약 그 중간값이 찾고자 하는 값이라면 중간 값을 반환하고 알고리즘을 종료한다.
- 2번으로 돌아가 반복한다. 만약 찾고자 하는 데이터가 없어서 가장 작은 데이터를 저장한 변수 값이 가장 큰 데이터를 저장한 변수 값을 초월해버린다면 종료한다.
int binarySearch(int* arr, int size, int key)
{
int lb = -1, ub = size-1, m;
while(lb+1 < ub)
{
m = lb+(ub-lb)/2;
if(arr[m] >= key) ub = m;
else lb = m;
}
return ub>=size? -1 : arr[ub]==key? ub : -1 ;
}컴퓨터에 저장 되어 있던 Binary Search 코드다. lb, ub는 lower bound, upper bound의 약자다. 최솟값, 최댓값의 인덱스를 각각 저장해둔 다음 lower bound가 upper bound 보다 밑에있는 동안 탐색을 반복한다. 이런 식으로 탐색을 하게 되면 굳이 처음부터 데이터를 하나 하나 찾지 않아도 빠른 시간 내에 데이터를 찾아낼 수 있다.
Outro
데이터의 양이 적다면 선형 탐색을 쓰든, 이분 탐색을 쓰든 크게 차이가 나지 않을 수도 있다. 그렇지만 경험 상 학부 과정에서 프로그래밍 문제를 풀 때, 엄청난 범위 내에서 값들을 찾아내야 하는 경우가 꽤나 잦았던 것으로 기억한다. 정렬되어있는 데이터 상에서 무언가를 찾는 경우라면 한번 써먹어 보는 게 어떨까?
