우리가 스무고개 게임을 해서 서로 비밀로한 숫자를 찾는다고 생각 해보자, 자 어떻게 해야 답을 찾을수 잇을까 ?
숫자의 제한이 1 ~ 1000 까지라고 했을 때 몇 가지 방법이 있다.
첫 번째, 1부터 1000까지 숫자를 하나 하나 물어본다. 오래걸리겠지만 확실하게 찾을수 있는 방법이다. 혹은 1000부터 1까지
1? 2? 3? 4? 5? 6? .... 1000?
두 번째, 그냥 감으로 때려 맞추는 거다.
34? 57? 154? 578? 275?
세 번째, 이진 탐색 법을 사용하는 것이다.
자 그럼 이진 탐색이 뭐냐 ?
우리가 스무고개 평소에 하는 방식이다.
예를 들어 우리가 몰래 정한 숫자가 678 이라고 하자.
상대방 |
우리 |
숫자가 500 보다 크거나 같니? |
응 |
숫자가 750보다 크거나 같니? |
아니 |
숫자가 675 보다 크거나 같니? |
응 |
숫자가 702보다 크거나 같니? |
아니 |
숫자가 688보다 크거나 같니? |
아니 |
675, 676, 677, ... 687,688 중 하나겠구나 |
그렇지 |
마지막에 상대방이 675 ~ 688 사이에 우리가 숨겨둔 값이 있는 것을 겨우 5번의 질문 만에 알아내었다.
이 과정에서 사용된 것이 바로 이진 탐색법, 즉 Binary Search 다.
적당한 값 ( 대체로 처음엔 가운데 Middle 값 을 사용한다 ) 을 확인해서, 이보다 큰지 작은지를 확인하고,
그 값을 기준으로 다시 새로운 범위를 정하고, 적당한값으로 다시 확인하고 이를 반복한다.
끝
그림으로 보는 것이 이해가 더 빠를 것이다.
답이 있을리가 없는 공간 |
아직 답이 있을 가능성이 있는 공간 |
확인하는 숫자 ( Middle 값 ) 은 기본적으로 Min 과 Max 를 더하고 2로 나눈 값이다.
찾고자 하는 수 7
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
자 이렇게 최악의 경우를 탐색을 해도 겨우 3번의 검사를 했을 뿐이다.
만약 1부터 하나하나 체크했다면 7번이 필요했을 것이고, 아무 숫자나 찝으면, 최악의 경우 10번이 걸렸을 것이다.
이진 탐색 방법은, 이진 탐색을 쓸수 있는 케이스에 대하여 거의 최고 수준의 효율을 보여준다.
따라서 문제를 보고 이에 이진 탐색을 사용할수 있는 문제라고 판단을 내릴수 있는 많은 연습이 필요할 것이다. 끝 !
