Page 16 -

표 1-1 A 씨 나이를 맞히는 절차(31살인 경우)
말하는 사람 문답 비고

당신 28살 미만입니까?
A 씨 아니오.
당신 32살 미만입니까? 28살 이상 36살 미만(28, 29, 30, 31, 32, 33, 34, 35)으로 줄었으므로 중간을 나눔
A 씨 네.

당신 30살 미만입니까? 28살 이상 32살 미만(28, 29, 30, 31)으로 줄었으므로 중간을 나눔
A 씨 아니오.
당신 31살 미만입니까? 30살 이상 32살 미만(30, 31)으로 줄었으므로 중간을 나눔

A 씨 아니오.
당신 31살입니다. 선택지는 하나뿐!
A 씨 정답입니다.

이 방법을 사용하면, A 씨가 31살일 경우가 아니라도 네 번 질문하면 반드시 나이를 맞힐 수 있습
니다(연습 문제 1.1). 즉, A 씨 나이가 20살 이상 36살 미만 중 어떤 숫자라 해도 ‘나이 후보를 반
으로 쪼개서 점점 줄여 간다’라는 알고리즘(방법, 절차)으로 나이를 맞힐 수 있습니다.

이렇게 반으로 쪼개서 어느 쪽인지 확인하는 방법은 이진 탐색법(binary search method)이라는 알고
리즘에 해당합니다. 나이 맞히기 게임을 사례로 들어 소개했지만, 실제로 컴퓨터 과학의 여러 분

야에서 사용하는 기초적이고 무척 중요한 알고리즘입니다. 이런 중요한 알고리즘이 컴퓨터뿐만
아니라 나이 맞히기 게임 같은 놀이에서도 효과를 발휘하다니 재미있지요? 이진 탐색법은 6장에
서 자세히 다룹니다.

그런데 “20살입니까? 21살입니까? 22살입니까? ...”와 같이 순서대로 물어보는 방법도 비효율
적이긴 하지만, 이 또한 알고리즘입니다. 선택지를 순서대로 조사하는 방법은 선형 탐색법(linear
search method) 알고리즘이라고 합니다. 선형 탐색법은 3.2절에서 설명합니다.

알고리즘의 탁월한 특징은 어떤 특정한 문제가 있을 때 그 어떠한 경우를 생각해도 ‘같은 방법으
로’ 답을 도출할 수 있다는 점입니다. 앞서 본 나이 맞히기 게임이라면 A 씨 나이가 20살이라도,

26살이라도, 31살이라도 나이 후보를 반으로 나눠서 어느 쪽인지 확인하는 똑같은 방법으로 답을
맞힐 수 있습니다. 이 세상은 이미 이런 시스템이 넘쳐 납니다. 내비게이션을 사용하면 현재 어느
위치에 있더라도 목적지까지 경로를 표시해 주고, 은행 구좌에 들어 있는 돈이라면 딱 지정한 만
큼 정확하게 출금할 수 있습니다. 이러한 시스템을 알고리즘이 지탱하고 있습니다.

032