유투브 방송 터키즈에서는 항상 방송 말미에 터키에 관련된 말도 안 되는 퀴즈를 낸다.
터키에서 가장 깊은 호수의 수심은?
터키의 유명 소설을 출간한 국내 출판사의 제목은? (객관식 보기 14개)
이런 식이다.
당연히 답을 알리가 없는 출연자가 당황해 하면 적당히 희망고문(?)을 주며 코미디로 소화한다.
기회를 3번 정도 주는데, 답이 숫자라면 업다운으로 추가 힌트를 준다.
이때 주어진 도전 기회에서 답에 근접하기 위한 효율적인 전략인 탐색 알고리즘이 필요하다.
정답이 1~100 사이에 있고 3번의 기회가 주어질 때 1, 2, 3... 혹은 100, 99, 98을 외치는 사람은 없다.
모두가 약속이나 한듯 중간값(median)을 부르거나, 나름의 근거를 갖고 괜찮아 보이는 숫자(pivot)을 고른다.
출연자들이 알고리즘을 공부를 하진 않았겠지만, 경험적으로 혹은 본능적으로 효율적인 방법을 선택하는 것이다.
끝 값에서 하나씩 순차적으로 탐색하는 방법을 단순 탐색(Simple Search)라고 한다.
1~100 중 답이 100인데 1부터 세기 시작했다면? 99개를 다 훑어야 답에 도달한다. 즉 최악의 경우 원소의 개수와 동일하게 n번 탐색한다. 탐색의 최대 횟수가 원소를 담은 리스트의 크기와 같을 때, 선형 시간(linear time)이 소요된다.
만약 중간값인 50부터 시작했다면, 중간값보다 정답이 위인지 아래인지 판단하여 그 다음 차례에서는 아래 절반인 25나 위 절반인 75를 선택한다. 이렇게 절반씩 쪼개어 나가면 최악의 경우 log2n번 만에 정답을 찾을 수 있게 된다. 즉 로그 시간(Logarithmic time)이 소요된다. 이런 탐색 방법을 이진 탐색(Binary Search)라고 부른다. 다만 이 방법을 사용하려면 원소들이 정렬되어 있어야 한다.
log2n을
이진 로그라고 부른다. 로그는 거듭 제곱의 반대말이므로 n이 2의 몇 제곱이냐를 묻는 것과 같다. 말로 풀어서 설명하면 2번을 몇 번 곱해야 n이 나오는 지 구하라는 뜻이다. 알고리즘의 Big-O 표기법에서 logn는 이진로그 log2n를 뜻한다.
이진 탐색을 python 코드로 짜면 아래와 같다.
# item은 찾아야 하는 값, low와 high는 탐색 범위
def binary_search(list, item):
low = 0
high = len(list)-1
# item이 찾아질 때까지 반복
while low <= item:
# 중간값 확인
mid = (low + high) // 2
guess = list[mid]
# item을 찾은 경우
if guess==item:
return mid
# 중간값이 item보다 큰 경우, 중간값 이하를 탐색
if guess > item:
high = mid-1
# 중간값이 item보다 작은 경우, 중간값 이상을 탐색
else:
low = mid+1
# item이 list에 없는 경우
return None
my_list = [1, 2, 3, 4, 5]
print binary_search(my_list, 2) # 1
print binary_search(my_list, 0) # None