[코테스터디] 이진 탐색

이진 탐색

이진 탐색(이분 탐색) 문제는 전체 데이터가 정렬된 상태에서 사용할 수 있는 알고리즘이다.

문제에서 순차탐색을 이용해 풀려고 했을 때, 탐색할 데이터가 너무 커서 탐색하기 어려울 때 이분탐색을 이용해 빠르게 문제를 풀 수 있다.

이진 탐색은 그러므로 O(logN)의 시간 복잡도로 빠르게 순회할 수 있다. 보통 이진 탐색 문제는 다익스트라와 연계하여 나올 수 있다.

 

중간 점 찾기

이진 탐색 문제는 시작점, 끝점, 중간점으로 변수 3개를 이용해 빠르게 데이터를 찾을 수 있다.

중간점은 시작점과 끝점을 합해 2로 나눈 값으로 웬만하면 외워두는게 좋다.

while left <= right:
	mid = (left + right) // 2 # mid 구하기

 

 

그 다음엔, 중앙 값으로 시작값이나 끝값을 갱신하면서 원하는 답을 찾아내는 코드를 작성하면 된다.

if x == mid:
  # x와 중앙값이 동일한 경우
elif x > mid:
  # x가 중앙값보다 큰 경우
    start = mid+1
else:
  # x가 중앙값보다 작은 경우
    end = mid-1

 

bisect

파이썬에서는 이진 탐색을 좀 더 쉽게 구현할 수 있게 `bisect`이라는 라이브러리를 제공한다. 하지만 너무 라이브러리에 의존하지 말도록 하자.

from bisect import bisect_left, bisect_right, insort_left, insort_right
"""
해당 array에서 x의 개수를 찾는 문제
"""

def count_by_range(array, left_value, right_value): 
    right_index = bisect_right(array, right_value) # 시퀀스, 값, {최소범위, 최대 범위}
    left_index = bisect_left(array, left_value) # bisect_left : 해당 값의 왼쪽 인덱스
    return right_index - left_index
    
n, x = map(int, input().split()) # 7, 2

array = [1, 1, 2, 2, 2, 2, 3]

count = count_by_range(array, x, x) # 4

• `bisect.insort_left(seq, value, lo=0, hi=none)` : 해당 위치(bisect_right)에 해당하는 값(value)에 넣을 수 있다.

구현

먼저 이진 탐색을 적용할 샘플 데이터를 만든다.

이진 탐색은 반드시 정렬된 상태에서 진행해야한다.

import random
array = random.sample(range(100), 10) # 1부터 100까지 10개의 데이터
array.sort() # 정렬

 

def binary_search(array, value):
    """
    해당 Array에 value 데이터가 있는지 확인하는 알고리즘
    """
    
    # 중앙값
    medium = len(array) // 2
    if value == array[medium]:
        return True
    else:
        if value > array[medium]:
            return binary_search(array[medium+1:], value)
        else:
            return binary_search(array[:medium], value)

---

문제 풀이

공유기 설치

대표 문제로 공유기 설치 문제를 보자.

N개의 집에 C개의 공유기를 설치한다고 할 때 두 공유기 사이의 최대 거리를 구하는 문제이다.

우선, 집 좌표의 수가 10억이 될 수도 있다. 순차 탐색으로는 당연히 풀 수 없기 때문에 이진 탐색으로 O(logX) 문제를 풀어야한다. 

 

먼저 집의 개수와 공유기의 개수, 그리고 배열에 집의 좌표(X)를 넣는다.

이진 탐색을 위해 해당 좌표들은 정렬 상태로 만들어줘야 한다.

n, c = map(int, input().split()) # 집, 공유기
array = []
for i in range(n):
    array.append(int(input())

array = sorted(array)

 

그러면 우리는 가장 가까운 거리와 가장 먼 거리를 확인할 수 있다.

공유기 간 최대 거리를 출력하기 위해 가장 앞단에 있는 1부터 공유기를 설치할 수 있는지 확인하면 된다.

만약 최대 거리 기준으로 공유기를 설치할 수 없으면 최대 거리를 줄여나간다.

near = array[1] - array[0]
far = array[-1] - array[0]
result = 0

 

먼저, 최대거리가 8이고 최소거리가 1일 때  중앙값은 4니까 중앙값 +  현재 값에 있는 곳에 공유기를 설치해보겠다.

공유기를 설치할 수 있지만 2개밖에 설치 못하므로 갱신할 필요 있다.

while(near <= far):
    mid = (near + far) // 2
    value = array[0]
    count += 1 # 현 공유기 설치 갯수
    for i in range(1, len(array)):
        if array[i] >= value + mid: # mid만큼 거리 보다 멀면
            count += 1 # 공유기 설치
    
    if count >= c: # 공유기를 설치할 수 있는 경우
        near = mid + 1
        result = mid
    else: # 공유기를 설치할 수 없는 경우
        far = mid - 1

 

결국엔 중앙값이 3일 때 최대거리로 공유기 3개를 설치할 수 있다.

 

 

 

징검다리 건너기

다음 징검다리 건너기 - 카카오 인턴십 2019 문제를 보자. 

징검다리를 건너는 배열의 크기는 200,000이하이고 즉, 친구들이 200,000개의 징검 다리를 건넌다고 가정하면 순차 탐색은 어려울 것이다. 이때 이진 탐색을 사용해야하는데 시작점과 끝점, 중간점을 주어진 디딤돌의 높이로 생각해서 `mid`명의 경우 `k`개로 디딤돌을 건널 수 있는지 확인해야한다. 만약 디딤돌을 건널 수 없어 `count`의 증가로 `k`값보다 크거나 같게 된다면 중단한다. 해당 다리를 건널 수 없으면 좌측 절반(1,2) 혹은 건널 수 있으면 우측 절반(4,5)로 이동하여 최대 건널 수 있는 인원을 구하면 된다.

 

def solution(stones, k):
    answer = 0
    left, right = 1, max(stones)
    # 징검 다리의 최대 높이가 5이므로 징검다리를 건널 수 있는 인원 또한 5일 것이다.
    
    while left <= right:
        count = 0
        mid = (left + right) // 2
        for stone in stones:
            if stone - mid <= 0:
                # 중앙 값보다 징검다리 수가 낮은 경우
                count += 1
            else:
                # 디딤할 수 있는 징검다리이기 때문에 초기화
                count = 0
            if count >= k:
                # 건너 뛸 수 있는 디딤돌 갯수가 3(k)를 넘어선 경우
                break
        
        if count < k:
            # 디딤 수가 최대 디딤수보다 낮은 경우 좀더 인원을 높일 수 있다.
            left = mid + 1
        else:
            # 그렇지 않은 경우 줄여나간다.
            answer = mid
            right = mid - 1
    return answer

 

 

📝 풀어보기 좋은 문제들

• 공유기 설치 - 백준
• 가사 검색 - KAKAO BLIND 2020
• 입국 심사 - 프로그래머스
• 징검다리 - 프로그래머스