[코드트리 챌린지] 4주차 - 이진탐색 / 컴퓨터와 함께하는 숫자 게임 2

https://www.codetree.ai/missions/8/problems/play-number-game-with-computer-2?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 이분 탐색의 원리를 사용하여 해결할 수 있습니다. 컴퓨터가 선택한 숫자를 찾기 위해 사람들은 항상 범위의 중간값을 선택합니다. 따라서 가능한 최소와 최대의 횟수를 구하기 위해 이분 탐색을 수행하면서 횟수를 계산합니다.

def game_duration(m, a, b):
    # 최소 횟수와 최대 횟수를 초기화합니다.
    min_turns, max_turns = float('inf'), 0

    # a부터 b까지의 모든 숫자에 대해 이분 탐색을 수행합니다.
    for num in range(a, b + 1):
        turns = 0
        left, right = 1, m

        # 이분 탐색을 시작합니다.
        while left <= right:
            # 중간값을 구합니다.
            mid = (left + right) // 2
            turns += 1
            if mid == num:
                break
            elif mid < num:
                left = mid + 1
            else:
                right = mid - 1

        # 최소 횟수와 최대 횟수를 업데이트합니다.
        min_turns = min(min_turns, turns)
        max_turns = max(max_turns, turns)

    return min_turns, max_turns

m = int(input())
a, b = map(int, input().split())
min_duration, max_duration = game_duration(m, a, b)
print(min_duration, max_duration)

이분 탐색을 활용한 숫자 게임

 이 게임에서는 컴퓨터가 1부터 m까지의 숫자 중 하나를 선택하고, 참가자들은 이 숫자를 찾아야 합니다. 참가자들은 항상 가능한 범위의 중간값을 선택하여 예측합니다. 컴퓨터는 예측한 숫자가 자신이 선택한 숫자보다 작은지, 큰지, 또는 같은지를 알려줍니다.
 이 문제의 핵심은 이분 탐색입니다. 이분 탐색은 정렬된 리스트에서 원하는 값을 효율적으로 찾는 알고리즘입니다. 이 게임에서도 참가자들은 이분 탐색의 원리를 사용하여 컴퓨터가 선택한 숫자를 찾습니다.

코드 설명:

• game_duration 함수는 m, a, b를 입력으로 받아 게임의 최소 지속 시간과 최대 지속 시간을 반환합니다.
• a부터 b까지의 모든 숫자에 대해 이분 탐색을 수행하며, 각 숫자를 찾는 데 필요한 횟수를 계산합니다.
• 이분 탐색을 수행하면서 예측한 숫자가 컴퓨터가 선택한 숫자보다 작은지, 큰지, 또는 같은지를 확인합니다.
• 최종적으로 게임의 최소 지속 시간과 최대 지속 시간을 반환합니다.

실력진단에서 나온 부족한 점을 점점 보완하면서 점수를 차근차근 올릴 수 있었다. 심화된 알고리즘을 학습하고 최대로 점수를 올려보아야겠다.