온라인 개인맞춤형 SIGMA!!
Blog | Tag | Local | Guest | Login | Write |  RSS
binary search에 해당되는 글 1건
2008.11.06 :: 알고리즘 코딩기법 - 4. 바이너리서치 2
알고리즘 코딩기법 - 4. 바이너리서치
2008. 11. 6. 22:00 :: 알고리즘코딩기법

안녕하세요.

오늘은 바이너리서치(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) Then
Solution = T
Break
End If
// T에 대한 값이 원하는 값보다 큰 경우 -> 상한을 T보다 1 작은 값으로 변경
If (value at T is greator than solution) Then
U = T - 1
End If
// T에 대한 값이 원하는 값보다 작은 경우 -> 하한을 T보다 1 큰 값으로 변경
If (value at T is less than solution) Then
L = T + 1
End If
End Repeat

Return Solution



구현1 - 배열에서 원소 검색(반복적 방법)

원소가 비내림차순으로 정렬된 배열에서 바이너리서치 - 반복적 방법
view plaincopy to clipboardprint?
  1. // 원소가 비내림차순으로 정렬이 되어 있는    
  2. // 크기 n의 배열 Array에서 key가 저장되어 있는 위치를    
  3. // 바이너리서치를 이용하여 리턴   
  4. // key가 없는 경우 -1을 리턴   
  5. int BinarySearchLoop(int Array[], int n, int key)   
  6. {   
  7.     int U = n-1;   
  8.     int L = 0;   
  9.     while (L <= U) {   
  10.         int T = (U + L) / 2;   
  11.         if (Array[T] == key) return T;   
  12.         if (Array[T] > key) U = T - 1;   
  13.         else L = T + 1;   
  14.     }   
  15.     return -1;   
  16. }  


구현 2 - 배열에서 원소 검색(재귀적 방법)

원소가 비내림차순으로 정렬된 배열에서 바이너리서치 - 재귀적 방법
view plaincopy to clipboardprint?
  1. // 원소가 비내림차순으로 정렬이 되어 있는   
  2. // 배열 Array에서 key가 저장되어 있는 위치를    
  3. // 바이너리서치를 이용하여 리턴   
  4. // key가 없는 경우 -1을 리턴   
  5. int BinarySearchRecursive(int Array[], int L, int U, int key)   
  6. {   
  7.     if (L > U) return -1;   
  8.     int T = (U + L) / 2;   
  9.     if (Array[T] == key) return T;   
  10.     if (Array[T] < key) return BinarySearchRecursive(Array, L, T-1, key);   
  11.     else return BinarySearchRecursive(Array, T+1, H, key);   
  12. }  



실수범위에서의 바이너리서치

위에서 정수를 기준으로 바이너리 서치를 하는 방법을 반복적 방법과 재귀적 방법으로 살펴보았는데요 상황에 따라서는 실수범위에 대해서 바이너리서치를 해야할 경우도 발생합니다. 뉴턴메소드(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) - 실수범위 바이너리서치(오차범위)
view plaincopy to clipboardprint?
  1. // ax^3 + bx^2 + cx + d = 0 의 해를 구합니다.   
  2. // 해는 [-1000000000, 1000000000]에 존재한다고 가정함   
  3. double EPSILON = 1e-9;   
  4. double CubicFunction1(double a, double b, double c, double d)   
  5. {   
  6.     double L = -1000000000;   
  7.     double U = 1000000000;   
  8.     double T = (L + U) / 2;   
  9.     while (U - L >= EPSILON) {   
  10.         double y = a*T*T*T + b*T*T + c*T + d;   
  11.         if (y > 0) U = T;   
  12.         else L = T;    
  13.     T = (L + U) / 2;   
  14.     }   
  15.     return T;   
  16. }  


구현 4 - ax^3 + bx^2 + cx + d = 0 의 해를 구함(허용 오차범위 1e-9) - 실수범위 바이너리서치(적당히반복)
view plaincopy to clipboardprint?
  1. // ax^3 + bx^2 + cx + d = 0 의 해를 구합니다.   
  2. // 해는 [-1000000000, 1000000000]에 존재한다고 가정함   
  3. double CubicFunction2(double a, double b, double c, double d)   
  4. {   
  5.     double L = -1000000000;   
  6.     double U = 1000000000;   
  7.     double T = (L + U) / 2;   
  8.     for (int i = 0; i < 100; i++) {   
  9.         double y = a*T*T*T + b*T*T + c*T + d;   
  10.         if (y > 0) U = T;   
  11.         else L = T;    
  12.     T = (L + U) / 2;   
  13.     }   
  14.     return T;   
  15. }  




문제를 풀어봅시다.

이론만 늘어서는 소용이 없겠죠?? 아는 것을 실전에 써 먹을 수 있는 준비가 되어있어야 진정 내것이라고 말할 수 있습니다.
우리같이 아래 문제를 풀어보아요

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


휴.. 이상으로 바이너리서치에 대해서 알아봤는데요.. 왠지 쓰고나니 마지막 문제가 좀 어려웠던게 아닌가 생각이 드네요 ^^;;

다음에는 주제를 약간 벗어나서 C++의 STL(Standard Template Library)에 대해서 포스팅을 해볼까 합니다.
뭐 제가 C++을 주로 사용하다 보니.. C++을 안쓰시는 분들한테는 전혀 도움이 되지 않겠지만 그래도 알아두면 좋겠지요 ㅎㅎ
저작자표시 동일조건

:
prev 1 next
:: total
:: today | :: yesterday
Designed by arisnoba
다솜돌이's Blog is powered by Daum

티스토리툴바