바이너리 서치의 기본과 예제

이분 탐색(Binary Search)은 이미 정렬된 리스트에서 특정 값을 빠르게 찾는 탐색 기법입니다. 이분 탐색을 더 확장하여 특정 조건을 만족하는 값을 찾는 매개 변수 탐색으로 응용할 수 있습니다. 매개 변수 탐색은 최적의 값을 찾는 문제에서 매우 유용하며, 많은 실전 문제에서 자주 등장합니다.

매개 변수 탐색은 이분 탐색의 개념을 응용하여 특정 조건을 만족하는 최적의 값을 찾는 방법입니다. 일반적인 이분 탐색은 주어진 값이 리스트에 있는지 여부를 확인하지만, 매개 변수 탐색은 조건을 만족하는 값의 범위를 구하는 데 초점을 맞춥니다.

매개 변수 탐색을 사용할 수 있는 조건은 주로 다음과 같습니다:

• 문제의 해가 범위 내에서 단조 증가 또는 감소하는 경우: 예를 들어 특정 길이 이상의 막대를 자를 수 있는 톱날 길이를 찾는 문제에서, 길이가 길어질수록 조건을 만족하는 수가 줄어듭니다.
• 조건을 만족하는 구간이 존재하는 경우: 조건을 만족하는 최솟값 또는 최댓값을 찾을 수 있습니다.

이분 탐색을 응용한 매개 변수 탐색의 동작 원리

매개 변수 탐색은 최적의 해를 찾기 위해 이분 탐색 범위를 점차 좁히면서 조건을 만족하는지 여부를 평가합니다. 이분 탐색의 기준이 되는 중간 값(mid)이 조건을 만족하는 경우, 조건을 만족하는 해가 더 작은 범위에 있는지, 더 큰 범위에 있는지를 판단해 탐색 범위를 줄여나갑니다. 이를 통해 탐색 범위가 줄어들고, 빠르게 최적의 해를 찾을 수 있습니다.

다음은 매개 변수 탐색을 사용하여 나무의 길이를 자르는 문제를 해결하는 예제입니다. 각 나무의 높이가 주어졌을 때, 특정 높이로 잘라 나머지 나무의 합이 목표치를 만족하는 최적의 톱날 길이를 찾습니다. 톱날 길이를 최적화하기 위해 매개 변수 탐색을 사용하여 해결할 수 있습니다.

Python 코드 예제:
def can_cut_tree(trees, height, target):
    # 주어진 높이로 자른 나무의 총 길이를 계산합니다
    total = sum(max(tree - height, 0) for tree in trees)
    return total >= target

def find_saw_height(trees, target):
    # 이분 탐색의 시작과 끝 범위를 설정합니다
    left, right = 0, max(trees)

    # 조건을 만족하는 최대 높이를 찾기 위해 이분 탐색을 수행합니다
    while left <= right:
        mid = (left + right) // 2

        # 조건을 만족하는 경우
        if can_cut_tree(trees, mid, target):
            left = mid + 1
        else:
            right = mid - 1

    return right

# 예제 사용
trees = [20, 15, 10, 17]
target = 7
print(find_saw_height(trees, target))  # 출력: 15
                

설명: find_saw_height 함수는 주어진 나무 배열에서 target만큼의 나무를 얻기 위해 톱날의 최적 높이를 이분 탐색으로 찾습니다. can_cut_tree 함수는 특정 높이로 잘라서 목표 길이를 만족하는지를 확인하여 이분 탐색의 조건 판단을 돕습니다.

매개 변수 탐색은 특정 조건을 만족하는 최적의 값을 찾는 문제에서 유용하게 사용됩니다. 일반적인 이분 탐색은 주어진 값이 존재하는지 여부를 확인하지만, 매개 변수 탐색은 조건을 만족하는 값의 범위나 최적 값을 찾는 데 중점을 둡니다.

예제 1: 최소 용량의 블루레이 만들기

여러 강의의 길이가 주어졌을 때, 모든 강의를 특정 개수의 블루레이에 담기 위해 각 블루레이의 최소 용량을 구하는 문제입니다. 이 문제는 매개 변수 탐색을 사용해 해결할 수 있습니다.

Python 코드 예제:
def can_distribute_lectures(lectures, capacity, blu_ray_count):
    current_sum = 0
    count = 1  # 첫 블루레이

    for lecture in lectures:
        if current_sum + lecture > capacity:
            count += 1
            current_sum = lecture
            if count > blu_ray_count:
                return False
        else:
            current_sum += lecture

    return True

def find_min_capacity(lectures, blu_ray_count):
    left, right = max(lectures), sum(lectures)

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

        if can_distribute_lectures(lectures, mid, blu_ray_count):
            right = mid - 1
        else:
            left = mid + 1

    return left

# 예제 사용
lectures = [1, 2, 3, 4, 5, 6, 7, 8, 9]
blu_ray_count = 3
print(find_min_capacity(lectures, blu_ray_count))  # 출력: 최소 용량
                

설명: find_min_capacity 함수는 모든 강의를 주어진 블루레이 개수 내에서 담을 수 있는 최소 용량을 매개 변수 탐색을 통해 찾습니다. can_distribute_lectures 함수는 현재 용량으로 블루레이에 강의를 담을 수 있는지를 확인하여 탐색 범위를 좁힙니다.

예제 2: 최대 속도로 특정 거리 도달

운전자가 특정 거리 target_distance를 일정 시간 내에 이동하려고 할 때, 도달 가능한 최대 속도를 매개 변수 탐색으로 구할 수 있습니다.

Python 코드 예제:
def can_reach_distance(speed, time, target_distance):
    return speed * time >= target_distance

def find_max_speed(time, target_distance):
    left, right = 0, target_distance

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

        if can_reach_distance(mid, time, target_distance):
            right = mid - 1
        else:
            left = mid + 1

    return left

# 예제 사용
time = 5
target_distance = 100
print(find_max_speed(time, target_distance))  # 출력: 도달 가능한 최대 속도
                

설명: find_max_speed 함수는 주어진 시간 내에 목표 거리를 도달할 수 있는 최대 속도를 매개 변수 탐색으로 찾습니다. can_reach_distance 함수는 주어진 속도와 시간이 조건을 만족하는지를 평가하여 탐색 범위를 좁혀줍니다.

매개 변수 탐색은 조건을 만족하는 최적의 값을 빠르게 찾을 수 있으므로, 정렬된 데이터에서의 범위 탐색 및 최적화 문제에서 강력한 도구로 사용됩니다. 그러나 특정 유형의 문제에서는 적용하기 어렵거나 탐색 범위 설정에 유의해야 합니다.

장점

• 조건을 만족하는 값의 범위를 효율적으로 찾을 수 있어, $$O(\log N)$$의 시간 복잡도로 탐색이 가능
• 단조 증가 또는 감소하는 조건을 가진 문제에서 범위 최적화를 할 수 있음

한계

• 탐색 범위가 명확하지 않거나 조건이 복잡한 문제에서는 적용이 어렵습니다
• 조건 설정에 따라 탐색 범위가 잘못되면 결과가 틀릴 수 있으며, 세심한 경계 조건 설정이 필요합니다