[ 알고리즘 ] 파이썬 이진탐색(Binary Search) 알고리즘, 숫자 맞추기

이진탐색 알고리즘은 정렬된 배열이나 리스트에서 특정한 값을 찾는 알고리즘입니다.

 

 동작방법

 

숫자를 기준으로 예를 들어 보겠습니다.

1부터 1000까지의 숫자 중에 임의의 값을 정하고

그 숫자를 맞춘다고 할 때

이진 탐색 알고리즘은 다음과 같은 과정을 거칩니다.

 

1. 시작값과 끝값의 중간값을 계산합니다.

2. 찾으려는 값이 계산한 중간값과 같다면 종료합니다.

3. 만약에 중간값이 찾으려는 값보다 작다면, 탐색 범위를 중간값 보다 작은 쪽으로 좁힙니다.

3-1. 만약에 중간값이 찾으려는 값보다 크다면, 탐색 범위를 중간값 보다 큰 쪽으로 좁힙니다.

4. 위 과정을 최소값이 최댓값보다 작거나 같을 때까지 반복합니다.

 

이는 우리가 숫자찾기 게임을 하는 것과 같습니다.

1부터 1000까지 숫자를 하나 생각한 것을 맞추어야 할 때

생각한 수가 500보다 작은지 같은지 큰지를 물어보고

대답에 따라서 다시 값을 설정해서 그 수보다 큰지 작은지 같은지 물어보는 것을 반복합니다.

 

반응형

 파이썬 코드

 

다음은 이진탐색 알고리즘을 사용하여

랜덤하게 생성된 숫자를 맞추는 게임을 파이썬으로 간단하게 만든 것입니다.

import random

def computer_guess():
  secret_number = random.randint(1, 10000)
  attempts = 0  
  low = 1 
  high = 10000 

  print(f"임의의 숫자를 생성했습니다. (정답: {secret_number})")

  while low <= high:
    guess = (low + high) // 2 
    attempts += 1
    print(f"시도 {attempts}: 컴퓨터는 {guess}를 추측했습니다.")

    if guess == secret_number:
      print(f"컴퓨터가 {attempts}번 만에 {secret_number}를 맞췄습니다!")
      break 
    elif guess < secret_number:
      print("더 큰 숫자입니다.")
      low = guess + 1 
    else:
      print("더 작은 숫자입니다.")
      high = guess - 1 
computer_guess()

 

위 코드에서 처럼 10,000개의 숫자에서 맞는 숫자를 찾으려면,

최대 14번의 질문을 하면 숫자를 맞출 수 있습니다.

 

1,000개의 숫자라면 10번

100개의 숫자라면 7번의 탐색이면 숫자를 맞출 수 있게 됩니다.

 

 마치며

 

여러 상황에서 이진탐색 알고리즘이 유용할 수 있습니다.

웹 페이지 스크래핑을 할 때 URL에 페이지 번호가 들어가는 경우도 있는데

최대 페이지 번호를 모를 경우

이진 탐색 알고리즘을 통해 페이지에 요청을 보내 최대 페이지를 알아내는 방법으로도 사용할 수 있습니다.

 

또한 데이터베이스에서 특정 데이터를 검색하거나,

사전에서 단어를 찾을 때와 같은 경우에도 유용하게 잘 사용할 수 있습니다.

 

참고로 이진 탐색 알고리즘은 정렬된 자료에서만 사용이 가능합니다.

숫자, 텍스트 등 가능하지만,

그것이 정렬되어 있어야 하고, 

그 값이 비교가 가능한 경우에 사용이 가능합니다.

여기를 방문하시면 더 많은 파이썬 관련 자료를 확인할 수 있습니다.

파이썬 공부하기