이분탐색 (Binary Search)

이분탐색이란?

정렬된 리스트 형태로 주어진 원소들을 분할정복 방법으로 절반씩 줄여가면서 원하는 값을 가진 원소를 찾는 방법이다. 최솟값과 최댓값의 중간값과의 비교를 통해 순환적으로 적용할 절반 크기의 부분배열을 선택한다. O(logN)의 시간복잡도를 가진다.

1. 정렬된 리스트와 target 값 34 가 있다. 인덱스 최소값 0과 최대값 10의 중간값은 5이므로 해당 인덱스에 있는 수 57과 34를 비교한다.

2. 52보다 34가 작으므로 인덱스 최대값을 4로 설정하여 오른쪽을 버린다. 이제 중간값은 2이고 해당 인덱스에 있는 수 30과 34를 비교한다.

3. 이번에는 30이 34보다 작으므로 인덱스 최소값을 3으로 설정하고 왼쪽을 버린다. 이제 중간값은 3이고 해당 인덱스에 있는 수가 34로 target을 찾았다!

Python 코드로 구현

# L : 정렬된 숫자 리스트, x : target, ind : 찾으려는 target의 인덱스
    left = 0
    right = len(L) - 1
    ind = 0

    while left <= right:
        mid = (left + right) // 2
        if L[mid] == x:
            ind = mid
            break
        elif L[mid] < x:
            left = mid + 1
        else:
            right = mid - 1

파라메트릭 서치 (Parametric Search)

매개변수를 이용한 탐색기법으로 최적화 문제를 결정문제로 바꾸어 해결하는 방법이다.
즉, 문제의 정답을 중간값일 것이다~ 하고 정해놓고 조건을 걸어(함수로 사용할 수 있음) 탐색을 마친 후 중간값이 답이 되는 탐색방법이다. 아래는 파라메트릭 서치를 적용할 수 있는 예제이다.

• 백준 1654번 랜선자르기
  https://www.acmicpc.net/problem/1654
  랜선의 갯수과 각각의 길이가 주어지고, 랜선 n개를 만든다고 했을 때 만들 수 있는 랜선의 최댓값을 구한다. 위에서 말한 것처럼 중간값을 정답으로 가정하고 조건에 맞는지 확인하는 방식으로 진행한다.

import sys

# 값 입력받기
k, n = map(int, sys.stdin.readline().split())
lines = [int(input()) for _ in range(k)]

answer = 0
left, right = 1, max(lines)

while left <= right:
    mid = (left + right) // 2    
    
    # 예상한 값으로 몇개의 랜선이 생기는 지 확인
    lan_cnt = 0
    for line in lines:
        lan_cnt += line // mid

    # 조건에 맞으면 답이다 
    if lan_cnt >= n:
        left = mid + 1
        answer = mid
    else:
        right = mid - 1

print(answer)