오늘 처음으로 소개할 알고리즘은 이진 탐색과 파라메트릭 서치입니다. 많은 분들이 이진 탐색에 대해선 많이 들어보셨을거라 생각하지만 파라메트릭 서치라는 알고리즘은 아마 생소하신 분들도 많을 것이라고 생각됩니다. 하지만 이 둘은 매우 유사하며 동일한 원리를 가지는 알고리즘이지만 그 활용에 있어서 차이를 보입니다.
이번 기회에 이진 탐색과 파라메트릭 서치에 관한 기본 개념부터 공통점, 차이점, 그리고 구현까지 알아보도로 하겠습니다.
1 | 이진 탐색(Binary Search)
이진 탐색은 정렬된 일련의 값들이 주어졌을 때 그 값들 중에서 원하는 값을 찾는 알고리즘이라고 할 수 있습니다.
이진 탐색은 처음에 중간값을 선택하여 그 값과 찾으려는 값을 비교하여 클 경우 선택했던 중간값을 최솟값으로, 작을 경우 중간값을 최댓값으로 하여 원하는 값을 찾을 때까지 이 과정을 반복하는 알고리즘입니다.
한 과정을 거칠 때마다 탐색하는 범위가 절반씩 줄어드므로 시간 복잡도는 O(log N)를 가지게 됩니다. 따라서 빠른 속도를 가진 탐색 알고리즘이며 대신 정렬된 값들이 아닐 경우 탐색을 할 수 없다는 단점을 가집니다.
이해를 돕기 위해 아래에 하나의 예시를 들도록 하겠습니다.( 예시는 편의상 반말로 진행하도록 하겠습니다..양해부탁드려요:) )
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
위와 같이 1부터 9까지 주어졌을 때 3라는 값을 찾는다 가정해보자.
이진 탐색의 흐름은 다음과 같다.
1. 중간값인 5가 3보다 큰지 작은지 검사한다.
2. 3 < 5 이므로 5부터 9까지는 배제하고 1부터 4까지 중에서 다시 중간값( (1+4)/2 = 2.5 -> 2)과 3을 비교한다.
3. 2 < 3 이므로 1부터 2까지는 배제하고 3부터 4까지 중에서 중간값( (3+4)/2 = 3.5 -> 3)과 3을 비교한다.
4. 일치하므로 탐색 종료.
아래는 C++ 로 구현한 이진 탐색 함수입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | int binarySearch(int array[], int value, int low, int high) { if(low > high) { return false; } int mid = (low+high) / 2; if(array[mid] > value) { return binarySearch(array, value, low, mid-1); } else if(array[mid] < value) { return binarySearch(array, value, mid+1, high); } else { return mid; } } | cs |
2 | 파라메트릭 서치(Parametric Search)
그렇다면 파마메트릭 서치는 어떨까요?
파라메트릭 서치는 이진탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘입니다.
이진탐색이 1부터 9까지의 값에서 3이라는 값을 찾는 알고리즘이라면 파라메트릭 서치는 1부터 9까지의 범위 내에서 3이라는 값(또는 원하는 조건에 부합하는 값)을 찾아가는 것이라는 차이가 있습니다. 따라서 주어진 값 중에서 탐색하는 이진탐색과는 다르게 파라메트릭 서치는 주어진 것이 값이 아니라 범위이기 때문에 특정한 상활을 최적화시키는 문제를 풀 때 용이하다는 장점을 가집니다.
실제로 파라메트릭 서치를 사용하면 최적화 문제를 결정 문제로 바꾸어 풀 수 있게 되어 문제 접근이 상당히 용이해집니다. 최적화 문제를 결정 문제로 바꾸어 푼다는 말은 주어진 상황에서 최솟값, 최댓값 등의 특정 값을 구하는 문제를 특정 값이 어떠한 조건을 만족하는지만 확인하면 되는 문제로 바뀐다는 의미입니다.
예를 들어봅시다.
배가 7시간마다 고파지는 사람이 하루를 배부르게 지내기 위한 최소한의 식사횟수는 몇회인지에 구하는 문제가 있다고 가정해보자.(글에서 주어지는 예시에서는 소수점 첫째자리까지만 계산한다.)
잠자는 시간등을 고려하지 않는다고 계산할 때 24시간을 식사횟수로 나눴을 때 7 또는 7에 가장 가까운 값이 나오도록 하는 것이 이 문제를 풀기 위한 조건이라고 할 수 있다.
0끼부터 10끼가지의 식사가 가능하다고 할 때
-첫 번째 단계
0 5 10 |
△(중간값)
범위가 0부터 10까지이므로 (0+10)/2 = 5를 중간값으로 하여 조건에 부합한지 검사해본다.
24 / 5 =4.8 이므로 원하는 값인 7보다 작다. 즉 나누는 값이 더 작아져야하므로 5 바로 밑에 있는 값인 4.9를 범위의 최댓값으로 하여 반복한다.
-두 번째 단계
0 2.4 4.9 |
24 / 2.4 = 10 이므로 원하는 값인 7보다 크다. 따라서 이번엔 중간값이였던 2.4 바로 윗값인 2.5를 최솟값으로 하여 2.4부터 4.9까지의 범위로 다시 반복합니다.
.
.
.
위의 과정을 반복하다보면 탐색범위와 중간값은 0-10(5) -> 0-4.9(2.4) -> 2.5-4.9(3.7) -> 2.4-3.6(3) -> 3.1-3.6(3.3) -> 3.4-3.6(3.5) -> 3.4-3.4(3.4) -> 3.4-3.3(3.3) 으로 변화할 것이며 범위의 시작값과 끝값의 대소관계가 역전되는 순간 탐색이 종료된다. 역전되기 직전 중간값인 3.4가 구하고자 하는 값이며 24를 7로 나눴을 때의 소수점 첫째짜리까지의 값이 3.4이므로 올바르게 탐색이 되었다.
위 예시의 핵심은 배부르게 지내기 위해 하루 최소 몇 회의 식사를 먹어야 하는가? 에 대한 최적화 문제가 하루에 식사를 R번 했을 때 배부르게 지낼 수 있는가에 대한 결정 문제로 바뀌었다는 것입니다. 문제의 조건이 복잡하거나 문제의 상황상 최적화시키기 위한 프로그래밍적 구현이 어려울 때는 이 파라메트릭 서치라는 알고리즘을 떠올리고 상황에 맞게 변형하여 이용해보시면 좋을 것 같습니다.
아래는 이 문제에서의 파라메트릭 서치 구현입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | float parametricSearch(float start, float end) { float mid, tempMid; while(start<=end) { mid = tempMid; tempMid = (start+end)/2.0; if(24/tempMid > 7) { start = tempMid+0.1; } else if(24/tempMid < 7) { end = tempMid-0.1; } else { break; } } return mid; } | cs |