[알고리즘] 5. 이진 탐색

/* '이것이 취업을 위한 코딩 테스트다' 책의 저자이신 나동빈 님의 예시와 제가 학교 수업에서 배운 내용을 바탕으로 정리했습니다. */

 

 

1. 이진 탐색 알고리즘

- 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가면서 데이터를 탐색하는 방법

(순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법)

 

- 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

- 단계마다 탐색 범위를 2로 나누느 것과 동일하므로 연산 횟수는 logN에 비례한다.

- 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장한다.

 

< 구현 >

def binary_search(start, end, target, array):
    if start > end:
        return None

    mid = (start + end) // 2

    if array[mid] == target:
        return mid
    elif array[mid] > target:
       	return binary_search(start, mid-1, target, array)
    elif array[mid] < target:
        return binary_search(mid+1, end, target, array)


# n : 원소의 개수, target : 찾고자 하는 값
n, target = map(int, input().split())
array = list(map(int, input().split()))

target_idx = binary_search(0, n-1, target, array)

if target_idx == None:
    print("cannot find")
else:
    print(target_idx + 1)

 

 

 

2. 파이썬 이진 탐색 라이브러리

- bisect_left (arr, x) : 정렬된 순서를 유지하면서 배열 arr에 x를 삽일할 가장 왼쪽 인덱스를 반환

- bisect_right (arr, x) : 정렬된 순서를 유지하면서 배열 arr에 x를 삽입할 가장 오른쪽 인덱스를 반환

 

from bisect import bisect_left, bisect_right

arr = [1, 2, 4, 4, 8]
x = 4

print(bisect_right(arr, x))
print(bisect_left(arr, x))

< 출력 > 

4

2

 

4의 값이 인덱스 2, 3을 가지므로 bisect_left를 하면 인덱스 2에, bisect_right를 하면 인덱스 4에 위치하게 된다.

 

 

- 이진 탐색 라이브러리를 응용하여 배열 내에 특정 원소가 몇 개 존재하는지 파악할 수 있다.

from bisect import bisect_left, bisect_right

array = [1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 8, 9]


def counting(array, target):
    return bisect_right(array, target) - bisect_left(array, target)


result1 = counting(array, 3)
result2 = counting(array, 4)

 

 

 

3. 파라메트릭 서치

- 파라메트릭 서치 (parametric search) : 최적화 문제를 결정 문데 ('예' 혹은 '아니오')로 바꾸어 해결하는 기법

- 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

- 일반적으로 코딩 테스트에서 파라매트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

 

- 예시 문제

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했습니다. 오늘은 떡볶이 떡을 만드는 날입니다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않습니다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줍니다.
절단기에 높이 (H)를 지정하면 줄지어진 떡을 한 번에 절단합니다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것입니다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm입니다. 손님은 6cm 만큼의 길이를 가져갑니다.
손님이 왔을 때 요청한 통 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는높이의 최댓값을 구하는 프로그램을 작성하세요.

 

< 정답 코드 >

N, M = map(int, input().split())
tteok = list(map(int, input().split()))


def cut_tteok(tteok, start_idx, end_idx, target):
    sum = 0

    if start_idx > end_idx:
        return None

    start = tteok[start_idx]
    end = tteok[end_idx]

    mid = (start + end) // 2

    for t in range(start_idx, end_idx+1):
        if tteok[t] > mid:
            sum += tteok[t] - mid

    if sum == target:
        return mid
    elif sum < target:
        return cut_tteok(tteok, start-1, end, target)
    elif sum > target:
        return cut_tteok(tteok, start+1, end, target)


tteok.sort()
H = cut_tteok(tteok, 0, N-1, M)

if H == None:
    print("impossible")
else:
    print(H)

< 출력 >

4 6
19 15 10 17
15

 

< 해설 >

- 이진 탐색과는 다르게 중간 값의 기준이 원소들이 아니라 최저값과 최고값이다. 목표하는 높이를 맞추기 위한 절단기의 높이가 꼭 배열 내의 원소값이라고 단정지을 수 없기 때문이다.

 

- 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정하면 된다.

- '현재 이 높이로 자른다면 조건을 만족할 수 있는가'를 확인한 후에 조건의 만족 여부 (예 / 아니오)에 따라서 탐색 범위를 좁혀서 해결할 수 있다.

- 절단기의 높이는 0 ~ 10억 정수 중 하나이다. 이렇게 큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려야 한다.

- 중간점의 값은 시간이 지날 수록 '최적화된 값'이 되기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 중간점의 값을 기록하면 된다.