이분 탐색

이분 탐색 알고리즘을 계속 풀어보는데 바리에이션들이 계속 등장해서 헷갈려서 정리해놓는다.

4가지 정도로 구분할 수 있다. 물론 모두 정렬된 배열에서만 동작함

기본 이분 탐색

정확히 일치하는 값이 있는지 찾는다

mid 값이 찾으려는 값과 같은지, 작은지, 큰지를 비교하여 탐색 범위를 절반씩 줄여가는 가장 기본적인 방법이다.

while (low <= high) {
    int mid = (low + high) / 2;
    if (arr[mid] == target) return mid; // 찾았을 때
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
}

Lower Bound, Upper Bound

Lower Bound는 찾는 값보다 크거나 같은 첫번째 원소의 위치를 찾고 (>=),

Upper Bound는 찾는 값보다 큰 첫번째 원소의 위치를 찾는다 (>)

while (low < high) {
    int mid = (low + high) / 2;
    if (arr[mid] >= target) { // upper bound이면 >
        high = mid; // mid가 답일 수 있으므로 포함해서 왼쪽 탐색
    } else {
        low = mid + 1; // mid는 답이 될 수 없으므로 제외하고 오른쪽 탐색
    }
}
// 결과는 low 또는 high

 

 

 

물론 반대로 사용해서 작거나 같은 값 (<=), 작은 값 (<)을 찾을 수도 있다

while (left < right) {
    int mid = (left + right) / 2;
    int now = list.get(mid);
    if (now <= find) {
        left = mid + 1;
    } else
        right = mid;
}
// 결과는 left 또는 right

이런 식으로 사용 가능하다

Parametric Search

이게 참 골치 아픈데... 특정 조건을 만족하는 최적해를 찾는 방법이다.

이 문제(백준 2805)에서 사용된다

 

이 문제의 조건을 보면, 특징 길이로 나무들을 잘랐을 때 잘린 윗 부분들을 가져갔을 때, 그 값이 조건을 만족하면서 최솟값이 되는 값을 찾아야 한다.

그러니까 조건을 만족하긴 했지만, 최적의 값이 아닐수도 있으니 이분탐색을 다시 수행하여 최적해를 찾는 것이다.

 

# 2805 나무 자르기
import sys

N, M = map(int, sys.stdin.readline().split())
prob = sorted(list(map(int, sys.stdin.readline().split())))


def get_cutting_trees(height: int):
    result = 0
    for tree in prob:
        if tree > height:
            result += (tree - height)
    return result


def binary_cutting():
    left = 1
    right = prob[N - 1]
    result_height = 0
    while left <= right:
        middle = (left + right) // 2  # 자를 나무의 높이
        result = get_cutting_trees(middle)
        if M <= result: # 더 적게 잘라야 하고, 자를 높이가 높아진다, 지금 자른 나무가 M보다 많다
            left = middle + 1
            result_height = max(result_height, middle)
        else: #더 많이 자를 수 있다, 자를 높이가 낮아진다, 자른 나무가 M보다 적다
            right = middle - 1

    print(result_height)


binary_cutting()

binary_cutting의 코드를 보면, 가져갈 수 있는 나무를 구한 다음, 이 값이 조건을 만족한다면 나무들을 자를 높이를 좀 더 높여본다.

조건을 만족하지 못한다면, 더 잘라야한다는 뜻이니까 right를 middle-1으로 설정한다. 이 과정을 반복하면서 정답값을 result_height에 조건을 만족할 때의 max 값을 저장해두어 답을 구한다

 

이외에도 여러 문제들을 풀어보면서 이분탐색이 정말 어렵게 내려면 한도끝도 없이 어렵게 나오는 것을 느꼈다. 코테 문제는 참 익숙해지지가 않는다