추측 게임

같은 문제에 적용한 서로 다른 알고리즘에서 효율성이 얼마나 다르게 나타나는지 알아보기 위해 간단한 게임을 해보기로 합시다. 컴퓨터는 1에서 16까지의 정수 중 무작위로 하나를 선택합니다. 컴퓨터가 고른 수를 알아낼 때까지 계속 그 수를 추측하는데, 각 추측마다 수가 높았는지 낮았는지를 알려 줍니다:

숫자를 맞췄다면, 다음 수를 추측하는데 사용했던 방법에 대해 생각해 보세요.

1을 고르고 2, 3, 4 를 고르는 방식으로 맞을 때까지 했을 수도 있을 겁니다. 이렇게 찾는 방법은 숫자들을 줄지어 있는것처럼 차례대로 검색하기 때문에 선형 검색(linear search)이라고 합니다. 꽤 확실한 방법이죠. 하지만 얼마나 많이 추측을 해야 할까요? 컴퓨터가 16을 고르게 되면 16번이나 추측을 해야 합니다. 또한 정말 운 좋게도 컴퓨터가 1을 골랐다면 첫 번째 추측에서 숫자를 맞출 수 있겠죠. 평균적으로는 어떨까요? 컴퓨터가 1에서 16까지의 수를 고를 확률이 같다면 평균은 8번일 것입니다.

그렇지만 단순히 1, 2, 3, 4,...처럼 일일이 추측하는 방법보다 더 효율적인 방법이 있을 겁니다. 그렇죠? 컴퓨터가 추측한 값이 큰지 작은지 얘기해 주니까 8부터 시작할 수 있습니다. 컴퓨터가 고른 숫자가 8보다 작다면 8이 너무 크다는 것을 알기 때문에 8에서 16까지의 수는 고려 대상에서 제외할 수 있습니다. 컴퓨터가 고른 숫자가 8보다 크다면 1에서 7까지의 수를 제외할 수 있습니다. 어느 쪽이든 숫자 범위의 반을 제외할 수 있겠죠. 다음번 추측에도 남아있는 숫자들 중에서 가운데 있는 수를 제거합니다. 이런 식으로 남아있는 숫자의 절반을 계속 제외합니다. 이런 방법을 이진 탐색(binary search)이라고 하는데 이 방법으로는 컴퓨터가 1부터 16중에 무슨 수를 고르던 최대 네 번의 추측 안에 수를 맞출 수 있습니다.

1에서 300까지의 수로도 한 번 해 보세요. 최대 아홉 번의 추측이면 맞출 수 있을 겁니다.

이번에는 수를 맞추는데 몇 번이나 필요했나요? 아홉 번 이상의 추측이 필요하지 않은 이유는 뭘까요? (수학적으로 설명할 수 있나요)?

어떻게 이진 검색으로 JavaScript 배열에서 특정 항목을 효율적으로 검색하는지 알아보겠습니다. 그전에 먼저, 조금 더 어려운 알고리즘을 살펴보겠습니다.

위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.