Page 14 -

1.1 알고리즘이란 무엇인가?
A LG O RI T HM & D AT A S TR U CT UR E S

알고리즘(algorithm)이란 문제를 푸는 방법, 절차를 말합니다. 이렇게 말하면 일상생활과 관련이

없는 어려운 개념처럼 느껴지겠지만, 실제로 알고리즘은 우리와 무척 가깝습니다. 간단한 예로 나
이 맞히기 게임을 생각해 봅시다.

나이 맞히기 게임

처음 만난 A 씨의 나이를 맞혀 봅시다. A 씨가 20세 이상 36세 미만이라는 건 알고 있습니다.

A 씨에게 ‘예, 아니오로 대답할 수 있는 질문’을 네 번 할 수 있습니다. 질문이 끝나면 A 씨가
몇 살인지 추측해서 대답합니다. 맞히면 당신의 승리, 틀리면 당신의 패배입니다.

과연 나이 맞히기 게임에서 이길 수 있을까요?

그림 1-1처럼 A 씨 나이는 20, 21, ..., 35살 사이의 16개 숫자 중 하나입니다. 바로 생각할 수

있는 방법은 “예”라는 답을 들을 때까지 “20살입니까? 21살입니까? 22살입니까?”와 같이 순서대
로 계속 물어보는 방법입니다. 하지만 이 방법으로 정답을 맞히려면 최악의 경우 16번을 물어봐
야 합니다. 만약 A 씨가 35살이라면 16번째 질문인 “35살입니까?”라는 질문에 마침내 “예”라고
대답하겠죠. 질문 가능한 횟수가 네 번이므로 이 방법으로는 게임에서 이기기가 어렵습니다.

그림 1-1 나이 맞히기 게임

դ ݻ ࢓ੌөਃ

઺ী
׹੉ ੓णפ׮

030