알고리즘 코딩기법 - 4. 바이너리서치
안녕하세요.
오늘은 바이너리서치(Binary Search) 의 코딩법에 대해서 알아보겠습니다.
숫자맞추기
참이슬을 까고나면 병뚜껑을 꼬은 다음에 손가락으로 쳐서 끊어지면 그 전사람이 벌주를 마시는 게임이 있죠?? 그리고 나서 벌주를 마신 사람은 병뚜껑에 있는 숫자를 보고 업&다운을 해서 그 숫자를 부른 사람이 또 벌주를 마십니다. (이거 우리 학교만 하나요?)
혹시나 모르시는 분이 있을까봐 부가 설명을 드리겠습니다.
참이슬 병뚜껑에는 [1, 50] 사이의 숫자가 찍혀있습니다. 한사람씩 숫자를 부르면 정답을 아는 사람이 정답에 지금 부른 숫자보다 큰지 작은지를 알려줍니다. 그 다음 사람은 좁혀진 범위 내에서 숫자를 다시 부릅니다. 그럼 범위가 점점 좁혀지고 누군가 숫자를 맞추게 되는데 그 사람이 벌주를 마시게 됩니다.
이 게임을 하고 있는 모든 사람이 화장실을 가고 싶어서 최대한 게임을 빨리 끝내기위해 최선을 다한다면 최대 몇 번째 사람까지 턴이 돌아갈까요??
그렇습니다. 정답은 6회입니다. 확인을 위해 검증을 해보도록 하겠습니다.
1회: [1, 50] - 25를 부름 [1, 24], [26, 50] 중 [26,50]이 숫자가 하나 더 많으므로 최악의 경우는 [26, 50]
2회: [26, 50] - 38을 부름 [26, 37], [39, 50] 모두 12개의 숫자가 남아있으므로 어떤 범위가 남아도 최소횟수는 같음
3회: [26, 37] - 31을 부름 [26, 30], [32, 37] 중 [32, 37]이 숫자가 하나 더 많으므로 최악의 경우는 [32, 37]
4회: [32, 37] - 35를 부름 [32, 34], [36, 37] 중 [32, 34]가 숫자가 하나 더 많으므로 최악의 경우는 [32, 34]
5회: [32, 34] - 33을 부름 [32, 32], [34, 34] 모두 하나만 남았음
6회: 하나만 남았습니다. 번호를 부르고 소주를 원샷하세요
모든 사람이 최선을 다 했을때 숫자가 하나가 남을때까지 게임이 지속된 예를 들었는데요. 이를 수식화 하여 풀 수 있습니다.
한 턴이 지날때 마다 숫자의 범위가 반씩 줄어들게 됩니다. n번째 턴에서 남은 숫자의 범위를 T(n)이라 하면,
T(n) = ceiling[ 0.5 * T(n-1) ] , ceiling은 올림입니다.
이 되고 식을 마스터정리(Master theorem)을 이용하여 풀면
T(n) = O(lg n) 이 됩니다. (여기서 lg는 밑이 2인 로그입니다)
아까 소주게임에 적용해 보면 n이 50 이므로 ceiling[ lg 50 ] = 6 이 되는것을 확인할 수 있습니다.
이처럼 바이너리서치를 적용하면 한 턴이 지날때마나 남아있는 후보의 범위를 반으로 팍팍 줄여나가기 때문에 검색을 해야하는 경우 아주 강력한 도구가 될 수 있습니다.
생각보다 어려운 바이너리서치
Knuth는 <Sorting and Searching>에서 이진탐색이 처음 발표된 것은 1946년이고, 버그가 없는 최초의 이진탐색 코드는 1962년이 되어서야 나타났다고 지적했습니다. 버그프리한 바이너리서치루틴도 보면 정말 간단합니다. 왜 이렇게 간단한걸 작성하는데 20년이나 걸렸는지 생각해 보면 그 만큼 버그없는 프로그램을 만든다는 것이 어려운 일이고 tricky한 버그를 발견하기도 쉬운일이 아닌가 봅니다.
아래의 의사코드를 봅시다.
INT L = 0 // 하한
INT U = N // 상한
INT Solution = -1 // 원하는 결과가 있는 위치 (-1: 원하는 결과를 찾을 수 없음)
// 하한이 상한보다 같거나 작으면 반복
Repeat Until (L <= U)
Begin Repeat
// 하한과 상한의 중간값을 취함INT T = (L + U) / 2
// 원하는 결과를 찾음
If (find solution at T) ThenSolution = T
BreakEnd If
// T에 대한 값이 원하는 값보다 큰 경우 -> 상한을 T보다 1 작은 값으로 변경
If (value at T is greator than solution) ThenU = T - 1End If
// T에 대한 값이 원하는 값보다 작은 경우 -> 하한을 T보다 1 큰 값으로 변경
If (value at T is less than solution) ThenL = T + 1End IfEnd Repeat
Return Solution
구현1 - 배열에서 원소 검색(반복적 방법)
원소가 비내림차순으로 정렬된 배열에서 바이너리서치 - 반복적 방법
// 원소가 비내림차순으로 정렬이 되어 있는
// 크기 n의 배열 Array에서 key가 저장되어 있는 위치를
// 바이너리서치를 이용하여 리턴
// key가 없는 경우 -1을 리턴
int BinarySearchLoop(int Array[], int n, int key) {
int U = n-1;
int L = 0;
while (L <= U) {
int T = (U + L) / 2;
if (Array[T] == key) {
return T;
} if (Array[T] > key) {
U = T - 1;
} else {
L = T + 1;
}
}
return -1;
}
구현 2 - 배열에서 원소 검색(재귀적 방법)
원소가 비내림차순으로 정렬된 배열에서 바이너리서치 - 재귀적 방법
// 원소가 비내림차순으로 정렬이 되어 있는
// 배열 Array에서 key가 저장되어 있는 위치를
// 바이너리서치를 이용하여 리턴
// key가 없는 경우 -1을 리턴
int BinarySearchRecursive(int Array[], int L, int U, int key) {
if (L > U) {
return -1;
}
int T = (U + L) / 2;
if (Array[T] == key) {
return T;
}
if (Array[T] < key) {
return BinarySearchRecursive(Array, L, T-1, key);
} else {
return BinarySearchRecursive(Array, T+1, H, key);
}
}
실수범위에서의 바이너리서치
위에서 정수를 기준으로 바이너리 서치를 하는 방법을 반복적 방법과 재귀적 방법으로 살펴보았는데요 상황에 따라서는 실수범위에 대해서 바이너리서치를 해야할 경우도 발생합니다. 뉴턴메소드(Newton's Method)가 그 예인데요 실수 범위에서 바이너리서치를 하는 경우에는 대체로 오차범위가 주어지고 그 오차범위내에 탐색범위가 들어갈때까지 반복을 하게됩니다.
반복적 방법이든 재귀적 방법이든 바이너리서치를 진행하면서 한 이터레이션이 지날때마다 탐색범위가 반으로 줄어들는 것을 이용하는 겁니다.
예를 들어 오차범위 1e-9 이내에서 답을 구하고 싶으면 low bound와 upper bound의 차이가 1e-9 보다 작아질때까지 반복을 하면 됩니다. 제가 개인적으로 더 추천하는 방법은 그냥 충분히 많이 이터레이션을 하는 것입니다. 무슨말이냐 하면 한 100번 정도 무조건 반복을 하는 겁니다.
이게 지금 무슨말을 하는 거냐!! 라고 생각할 수도 있는데요.. 바이너리서치의 이터레이션을 100번을 반복하면 탑색범위가 1/(2^100)까지 좁혀지게 됩니다. 이 정도 탑색범위라면 1e-9 이내로 들어가지 않을까요?? 뭐 상황에 따라 적잘하게 이터레이션 횐수를 정해주면 됩니다만 제 생각엔 최악의 경우에도 1000번 정도면 충분할것이라 생각합니다.
그렇다면 오차범위 내에 들어갈때까지만 비교하면 될것을 왜 쓸데없이 반복을 하냐라고 물어볼수도 있는데요.. 제가 적당히 큰 횟수만큼 반복하는 것을 권장하는 이유는 오차범위 비교 방법은 실수연산의 특성상(precision error가 생기죠) 오차범위내로 수렴하지 못해 무한루프에 빠질 가능성이 있기 때문입니다.
아래에서 3차 방정식의 해를 바이너리서치를 이용하여 구하는 예를 보겠습니다.
구현 3 - ax^3 + bx^2 + cx + d = 0 의 해를 구함(허용 오차범위 1e-9) - 실수범위 바이너리서치(오차범위)
// ax^3 + bx^2 + cx + d = 0 의 해를 구합니다.
// 해는 [-1000000000, 1000000000]에 존재한다고 가정함
double EPSILON = 1e-9;
double CubicFunction1(double a, double b, double c, double d) {
double L = -1000000000;
double U = 1000000000;
double T = (L + U) / 2;
while (U - L >= EPSILON) {
double y = a*T*T*T + b*T*T + c*T + d;
if (y > 0) {
U = T;
} else {
L = T;
}
T = (L + U) / 2;
}
return T;
}
구현 4 - ax^3 + bx^2 + cx + d = 0 의 해를 구함(허용 오차범위 1e-9) - 실수범위 바이너리서치(적당히반복)
// ax^3 + bx^2 + cx + d = 0 의 해를 구합니다.
// 해는 [-1000000000, 1000000000]에 존재한다고 가정함
double CubicFunction2(double a, double b, double c, double d) {
double L = -1000000000;
double U = 1000000000;
double T = (L + U) / 2;
for (int i = 0; i < 100; i++) {
double y = a*T*T*T + b*T*T + c*T + d;
if (y > 0) {
U = T;
} else {
L = T;
}
T = (L + U) / 2;
}
return T;
}
문제를 풀어봅시다.
이론만 늘어서는 소용이 없겠죠?? 아는 것을 실전에 써 먹을 수 있는 준비가 되어있어야 진정 내것이라고 말할 수 있습니다.
우리같이 아래 문제를 풀어보아요
Equilibrium Point
직선상에 N개의 행성들이 위치해 있습니다. i 번째 행성은 x[i] 좌표에 있고, m[i] 만큼의 질량을 가지고 있으며, 각각의 행성들은 매우 강한 힘에 의하여 고정되어 있습니다. 모든 행성은 x좌표를 기준으로 비내림차순으로 정렬되어 주어집니다.
질량이 m1, m2인 두 물체 사이의 거리가 d일 때, 두 물체는 서로 F = G * m1 * m2 / d^2 의 힘으로 서로 잡아당기는 만유인력이 작용합니다. (G는 양의 상수이다.) 어떤점 P를 기준으로 만유인력의 벡터합이 0이 되는 P의 위치를 equilibrium Point라고 부릅니다.
N개의 점이 있을 때, N-1개의 Equilibrium Point가 존재합니다. 이러한 Equilibrium Point들을 오름차순으로 정렬하여 소수점이하 9자리까지 출력하시오.
힌트: 각 Equilibrium Point는 이웃한 행성과 행성사이에 하나씩 존재합니다.
출처: TopCoder - Single Round Match 421
i번째 Equilibrium Point(이하 EP)는 EP의 왼쪽에 i개의 행성이 있고 오른쪽에 n-i개의 행성이 있습니다.
EP의 위치를 x'이라 하고 가상의 질량 m'을 부여하면 EP의 왼쪽에 위치한 행성으로부터 받는 중력은 다음과 같습니다.
F1 = ∑ G * m' * m[k] / (x[i] - x')^2 = G * m' * ∑ m[k] / (x[i] - x')^2 (k = 0....i)
EP의 오른쪽에 위치한 행성으로부터 받는 중력은 다음과 같습니다.
F2 = ∑ G * m' * m[k] / (x[i] - x')^2 = G * m' * ∑ m[k] / (x[i] - x')^2 (k = i+1....n)
EP는 중력이 0이 되는 위치이므로 양쪽에서 받는 중력이 같아야 합니다. 따라서 F1 = F2인 x'을 찾아야합니다.
F1 = F2
G * m' * ∑ m[k] / (x[i] - x')^2 (k = 0....i) = G * m' * ∑ m[k] / (x[i] - x')^2 (k = i+1....n)
양변의 G * m' 을 소거하면,
∑ m[k] / (x[i] - x')^2 (k = 0....i) = ∑ m[k] / (x[i] - x')^2 (k = i+1....n)
m과 x는 주어지므로 위 식에서 미지항은 x'밖에 없습니다. x'은 뉴턴메소드(바이너리서치)를 이용하여 구할 수 있습니다.
void EquilibriumPoint(double x[], double m[], int n) {
// n-1개의 Equilibrium Point가 존재함
for (int i = 0; i < n-1; i++) {
double L = x[i];
double U = x[i+1];
double T = (L + U) / 2;
// 적당히 큰 횟수 반복(200회 -> 오차범위 1/(2^200))
for (int j = 0; j < 200; j++) {
double F1 = 0;
double F2 = 0;
// 왼쪽에 위치한 행성의 중력의 합
for (int k = 0; k <= i; k++) {
F1 += m[k] / pow(x[k] - T, 2.0);
}
// 오른쪽에 위치한 행성의 중력의 합
for (int k = i+1; k < n; k++) {
F2 += m[k] / pow(x[k] - T, 2.0);
}
if (F1 > F2) {
// 왼쪽에서 더 큰 중력을 받음 -> EP는 좀 더 오른쪽에 있다
L = T;
} else {
// 오른쪽에서 더 큰 중력을 받음 -> EP는 좀 더 왼쪽에 있다.
U = T;
}
T = (L + U) / 2;
}
printf("%.9f\n", T);
}
}
휴.. 이상으로 바이너리서치에 대해서 알아봤는데요.. 왠지 쓰고나니 마지막 문제가 좀 어려웠던게 아닌가 생각이 드네요 ^^;;
다음에는 주제를 약간 벗어나서 C++의 STL(Standard Template Library)에 대해서 포스팅을 해볼까 합니다.
뭐 제가 C++을 주로 사용하다 보니.. C++을 안쓰시는 분들한테는 전혀 도움이 되지 않겠지만 그래도 알아두면 좋겠지요 ㅎㅎ