[백준 13777번: Hunt The Rabbit] 파이썬 풀이_이분탐색

13777번: Hunt The Rabbit

문제

Mr Farkle was brought up on a farm and spent quite a bit of time in his youth hunting rabbits! He now teaches maths and computing, and came up with a hunting game to help his students learn about the binary search.

He put 50 envelopes at the front of the room, numbered sequentially from 1 to 50. Inside one he hid a rabbit – not a real one, of course, just a card with a rabbit picture on it! He then put cards in all the other envelopes so that if an envelope was chosen with a number lower than the one holding the rabbit, the card would read “Try a higher number”, otherwise the card would read “Try a lower number”.

Students have to find the rabbit using a binary search, and write down the numbers of all the envelopes they open (in order) during their search. Remember, in a binary search you have to pick the middle envelope in the range you are searching. This is easy to find if there is an odd number of envelopes, but with an even number, you have to choose the lower numbered of the two middle envelopes. That means 25 will always be the first envelope checked.

Mr Farkle은 농장에서 자랐고 토끼를 사냥하는 데 많은 시간을 보냈습니다. 그는 이제 수학과 컴퓨터를 가르치고 학생들에게 이분탐색을 가르치기 위해 hunting game을 생각해 냈습니다. 그는 방의 앞쪽에 1부터 50까지의 번호가 쓰여진 50개의 봉투를 넣었습니다.

그 중 하나의 봉투 안에 그는 토끼 그림이 그려진 카드를 숨겼습니다. 그리고 나서 그는 다른 모든 봉투에 카드를 넣었고, 만약 토끼를 잡고 있는 봉투보다 낮은 번호를 선택했다면, 그 카드는 "더 높은 번호를 시도해 보세요"라고 쓰여지고, 그렇지 않으면 그 카드는 "더 낮은 번호를 시도해 보세요"라고 쓰여져 있습니다.

학생들은 이진법 검색을 사용하여 토끼를 찾아야 하고, 검색하는 동안 여는 모든 봉투의 번호를 순서대로 적어야 합니다. 이진법 검색에서는 검색하는 범위의 가운데 봉투를 선택해야 합니다. 홀수 개의 봉투가 있는지 쉽게 찾을 수 있지만 짝수 개의 경우 두 개의 가운데 봉투 중 낮은 번호를 선택해야 합니다. 이는 25가 항상 첫 번째로 확인되는 봉투라는 것을 의미합니다.

입력

Each line of input will be a single number in the range 1 to 50 inclusive, it being the number of the envelope in which Mr Farkle has hidden the rabbit. The final input will be 0 which should not be processed.

입력의 각 줄은 Mr Farkle가 토끼를 숨긴 봉투의 번호인 1에서 50 사이의 숫자이다. 마지막 입력은 처리되지 않는 0으로 끝난다.

출력

For each line of input, output the numbers of all envelopes opened, in the order they were opened, until the rabbit is found. Each number must be on the same line separated by a space from the previous number.

각 입력 줄에 대해 열린 모둔 봉투의 번호의 토끼를 찾을 때까지 열린 봉투의 번호를 순서대로 출력한다. 각 번호는 이전 번호와 공백으로 구분되며, 같은 줄에 있어야 한다.

 

---

풀이

x = list()
result = list()

while True: # 여러 줄의 입력을 a가 0일 때까지 받아서 x라는 리스트에 넣음
  a = int(input())
  if (a == 0):
    break
  x.append(a)

def binary_search(target, array):  # 이분탐색 함수
    left, right = 0, len(array) - 1

    while left <= right:
        mid = (left + right) // 2

        if array[mid] == target:
            print(array[mid],end=' ')
            break
        elif array[mid] < target:
            print(array[mid],end=' ')
            left = mid + 1
        else:
            print(array[mid],end=' ')
            right = mid - 1
    return -1
    
arr = [i for i in range(1, 51)] # 1~50까지의 번호를 arr이라는 배열에 저장

for i in x:  # x 리스트의 요소를 하나씩 꺼내서 
  binary_search(i, arr)  # i를 1~50까지의 숫자 리스트에서 이분탐색
  print()

 

- 이분탐색을 활용하기 위해 binary_search라는 함수를 사용

- while문을 이용해 여러 줄의 입력을 a가 0일 때까지 받아서 x라는 리스트에 넣고, x 리스트의 요소를 for문으로 하나씩 꺼내서 이분탐색으로 탐색

 

---

이분탐색이란?

이분 탐색(Binary Search)은 특정한 값을 찾는 탐색 알고리즘 중 하나로, 주로 정렬된 배열에서 사용된다. 배열 내에서 원하는 값을 효율적으로 찾는 방법으로, 각 단계마다 탐색 범위를 반으로 줄여가며 탐색하는 특징을 가지고 있다. 이로 인해 탐색 속도가 매우 빠르며, 탐색 범위가 큰 경우에도 빠른 검색이 가능하다.

 

이분 탐색의 동작 원리

1. 정렬된 배열에서 시작한다.
2. 배열의 중간 인덱스를 찾는다.
3. 중간 인덱스의 값을 확인하여 찾고자 하는 값과 비교합니다.

• 만약 중간 값이 찾고자 하는 값과 일치하면, 탐색을 종료하고 해당 인덱스를 반환한다.
• 중간 값이 찾고자 하는 값보다 크다면, 배열의 왼쪽 절반에서 탐색을 계속한다.
• 중간 값이 찾고자 하는 값보다 작다면, 배열의 오른쪽 절반에서 탐색을 계속한다.

4. 탐색 범위를 반으로 줄여가며 2단계로 돌아가 반복한다.

 

파이썬에서 이분탐색의 구현

(재귀함수 사용)

def binary_search_recursive(arr, target, low, high):
    if low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            return binary_search_recursive(arr, target, mid + 1, high)
        else:
            return binary_search_recursive(arr, target, low, mid - 1)
    else:
        return -1

# 예시 사용
sorted_array = [2, 5, 7, 12, 16, 23, 32, 45, 50, 65]
target_value = 23

result = binary_search_recursive(sorted_array, target_value, 0, len(sorted_array) - 1)

if result != -1:
    print(f"타겟 값 {target_value}의 인덱스: {result}")
else:
    print("타겟 값이 배열에 존재하지 않습니다.")

(반복문 사용)

def binary_search_iterative(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

# 예시 사용
sorted_array = [2, 5, 7, 12, 16, 23, 32, 45, 50, 65]
target_value = 23

result = binary_search_iterative(sorted_array, target_value)

if result != -1:
    print(f"타겟 값 {target_value}의 인덱스: {result}")
else:
    print("타겟 값이 배열에 존재하지 않습니다.")

 

 

참고 링크

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

 

[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)