[Python] SW Expert Academy - 4839. 이진탐색

SW Expert Academy 4839번 이진 탐색 문제는 두 사람에게 책에서 각자 찾을 페이지 번호를 알려주면, 이진 탐색만으로 지정된 페이지를 먼저 찾는 사람이 이기는데, 이긴 사람이 누구인지 알아내 출력하는 문제이다. 이진 탐색 알고리즘에 관한 문제로 난이도는 D2다.

 

SW Expert Academy 4839번 이진 탐색 문제 정보

알고리즘 분류

- 이진 탐색 Binary Search

난이도

- D2

 

이진 탐색 문제 요약

• 책의 전체 쪽수와 두 사람이 찾을 페이지가 주어졌을 때 이진 탐색만으로 지정된 페이지를 먼저 찾은 이긴 사람이 누구인지 구하여 출력한다.
• 책의 전체 쪽수 P, A와 B가 찾을 페이지 번호의 범위는 1 이상 1000 이하이다.
• 비긴 경우는 0을 출력한다.

문제 풀이 과정

• 이진 탐색 기능을 가진 함수를 구현한다.
• 목표 페이지에 따라 중간 페이지를 기준으로 왼쪽 또는 오른쪽 영역의 중간 페이지를 다시 찾아가면서 이진 탐색하고, 목표 페이지와 중간 페이지가 같을 때 탐색을 끝낸다.
• 테스트 케이스 번호, 이긴 사람 or 0을 출력한다.

코드 및 설명

• binary_search - 이진 탐색 알고리즘 구현 함수 (파라미터: 지정된 페이지, 탐색 범위의 첫 페이지, 마지막 페이지)
• binary_search2 - 이진 탐색 알고리즘 구현 재귀 함수 (파라미터: 지정된 페이지, 탐색 범위의 첫 페이지, 마지막 페이지, 이진 탐색 횟수)
• cnt - 이진 탐색 횟수

#1 이진 탐색 일반 함수
def binary_search(goal, left, right):
    cnt = 0
    while True:
        center = (left + right) // 2
        if goal < center:
            right = center
        elif goal > center:
            left = center
        else:
            break
        cnt += 1
    return cnt

#2 재귀 함수로 구현한 이진 탐색
def binary_search2(goal, left, right, cnt=0):
    center = (left + right) // 2
    if goal < center:
        right = center
        cnt += 1
        return binary_search2(goal, left, right, cnt)
    elif goal > center:
        left = center
        cnt += 1
        return binary_search2(goal, left, right, cnt)
    else:
        return cnt

T = int(input())
for tc in range(T):
    P, A, B = map(int, input().split())
    cntA = binary_search(A, 1, P)
    cntB = binary_search2(B, 1, P)

    if cntA > cntB:
        print("#%d B" % (tc + 1))
    elif cntA < cntB:
        print("#%d A" % (tc + 1))
    else:
        print("#%d %d" % (tc + 1, 0))

---

SW Expert Academy 4839번 이진 탐색 문제는 binary search algorithm에 관한 문제이며 파이썬을 사용하였다. 난이도는 D2이다. 이진 탐색 재귀 함수와 일반 함수를 모두 구현해봄으로써 재귀 함수를 공부할 수 있었다.