[Algorithm] Binary Search(이분 탐 정리 + 추천 문제 list(Python)

0. 들어가며

이번에 소개할 알고리즘은 Binary Search(이분 탐색)입니다.

제가 몇몇 사람들에게 Binary Search를 가르쳐 줄 때마다 많이 헷갈려 하는 알고리즘들 중 하나 였습니다.

가장 큰 이유는 사람마다 다른 알고리즘의 구현 방식 때문이였는데, 이번에 모든 경우에도 적용 가능한 Template 같은 코드를 이용해 설명할 예정이니 도움이 되었으면 좋겠습니다.

 

저는 알고리즘을 공부하며 크게 2가지의 알고리즘이 있다고 생각하는데요. 바로 찐 알고리즘과 그외 입니다.

• 찐 알고리즘은 바로 누군가가 "특정 상황에 적용 가능한 일련의 규칙이나 여러 행위 그리고 더 나아가 공식화한 형태로 표현한 것"
  이라고 생각합니다. 

예를 들면 다익스트라, 크루스칼, A* 알고리즘 등이 있습니다.

언급된 알고리즘들은 "특정 상황(ex: 최단경로)"에서 "일련의 규칙이나 여러 행위(ex: 다익스트라 : 현재 갈 수 있는 최단 경로에서 방문 가능한 노드를 방문하며 각 노드의 최단 경로 갱신을 반복)"하면 원하는 결과를 얻을 수 있습니다.

그러면 Binary Search 알고리즘은 위의 2가지 중에서 어떤 것에 해당하냐면 "찐 알고리즘"입니다.

그래서 해당 알고리즘을 구현하는 Template 같은 코드를 암기하고 있으면 크게 어렵지 않게 적용해 많은 문제를 해결할 수 있습니다.

Binary Search 알고리즘을 사용할 때 가장 유념해야 할 부분은 바로

"주어진 Data를 Parameteric Search 가 가능하도록 결정 문제로 변환해 해석한 뒤 Binary Search를 하는 것"

입니다.

아래에서 위의 문장을 자세히 설명할 예정이니 끝까지 읽어주시면 감사할 듯 합니다.

---

1. Binary Search(이분 탐색)이란.

아마 대부분의 이분 탐색을 배울 때 큰 맥락으로 주어진 Data를 이분법적으로 나누며 원하는 데이터를 찾는 것 정도로 기억하고 계실 겁니다. 사실 여기에서 몇 가지 누락되어 있습니다. 

이분 탐색(Binary Search)은 결정 문제(Decision Problem)의 답이 이분적으로 나뉠 때 사용할 수 있는 탐색 기법입니다. 

여기서 결정 문제란 주어진 문제에 대해서 정답이 Yes or No를 의미하며 보통 1개의 parameter를 가집니다.

예를 들어서 BOJ 1920 수 찾기 문제를 보겠습니다.

주어진 Data에서 X라는 정수가 존재하는지 알아내는 알고리즘을 짜면 됩니다.(Hash Map등을 사용하면 되지만, 여기선 Binary Search로 찾는 것으로 하겠습니다...)

위 문제의 조건(현재 고려하는 Data가 X인가요?)을 Data에 적용하면 결과는 Yes, No로 나오고, 전체의 결과가 No라면 최종적인 답도 No이고 1개라도 Yes라면 Yes입니다.

이것을 배열(List)의 형식으로 표현하면 [False, False, ..., False, True or False, False, ..., False ]처럼 나옵니다.

하지만 문제의 조건을 조금 변경해서 적용해보겠습니다. 오름차순 정렬도 적용하겠습니다.

현재 고려하는 Data가 X이상인가요?라는 조건을 적용해 Data의 결과를 보면 다음과 같습니다.

[False, False, ..., False, True, Ture, ... True]

데이터가 일정 위치를 기점으로 False, True가 나뉘는 것을 볼 수 있습니다. 이렇게 결정 문제의 답이 두 구간으로 나뉘는 것을 "이분적이다"라고 표현하고, 이러한 결정 문제에 대해 이분 탐색을 통해 Data가 바뀌는 경계를 찾을 수 있습니다.

 

즉, 이분 탐색은 이러한 정답이 변화하게 되는 경계를 찾는 알고리즘이라고 할 수 있습니다. 그러기 위해 주어진 Data에 결정문제를 적용해 이분적으로 만들어야 하는 과정을 선행해야 합니다. 이 부분 또한 이분 탐색 문제를 해결하는 굉장히 중요한 요소이기 때문에 문제를 해결하며 이 부분에 대해서도 고민해보는 것을 추천드립니다.

 

2. 이분 탐색 구현 방법

이분 탐색은 [True, False] 혹은 [False, True]가 되는 이러한 경계를 찾는 알고리즘이라고 했습니다. 

먼저 이분 탐색을 적용할 범위(Low, High)를 설정해야합니다. 이때 조건을 결정문제로 변환 했을 때 True, False를 return 해주는 함수를 f라 할 때 f(Low) != f(High)여야 합니다. 주어진 원소가 모두 True, False일 경우 주어진 범위 밖으로 True 혹은 False가 있어 최종적으로는  f(Low) != f(High)입니다. 아래에서 예를 들어 설명해보겠습니다.

 

이분 탐색의 아이디어는 경계를 포함하는 구간 [Low, High]를 잡은 뒤 해당 구간의 길이를 절반씩 줄여나가며
최종적으로 Low + 1 = High이지만 f(Low) != f(High)인 상태로 만들어 이러한 경계를 찾는 것입니다.

여기서 경계를 줄이는 방법은 다음과 같습니다.

최종적으로 Low + 1= High를 만족하기 이전에 Low + 1 < High를 만족하는 동안 [Low, High]인 범위를 [Low, Mid] 혹은 [Mid, High]로 바뀌게 됩니다. 여기서 [Low, Mid]로 바꾸는 경우는 f(Mid) == f(High)인 경우고, f(Low) == f(Mid)인 경우엔 [Mid, High]로 바꾸면 됩니다. 쉽게 생각하면 어쨌든 [Low, High] 내부에 경계가 있어야 하므로 계속 f(Low) != f(High)를 유지시키도록 서칭 공간을 바꾸면 됩니다.

이렇기 때문에 시간 복잡도의 경우 데이터를 절반씩 줄여나가며 탐색을 하기 때문에,
데이터의 크기를 N이라 할 때 O(\log N)이 걸리게 됩니다. 

 

Python 코드로는 일반적으로 다음과 같이 진행됩니다.

def binary_search(L, R):
    def possible():
        if condition : return True
        else : False
    while L + 1 < R:
        mid = (L + R) // 2
        if possible(mid) : L or R = mid
        else : L or R = mid
    return L or R

 

보통 L, R 범위를 잡을 때 실수를 많이 하게 되는데, 여기서 생각해야하는 것은 탐색할 영역 내에 경계가 있어야 한다는 것입니다.

그런데 만약 Data가 결정 문제로 바꿨을 때 모두 True 혹은 모두 False라면 경계가 없지 않나? 싶을 수 있습니다.

하지만 쉽게 생각해 범위를 한칸 늘려 False나 True가 존재한다고 생각해 탐색을 진행하면 됩니다.

예를 들어 1~50까지 숫자 카드에서 100이 존재하는가?라는 문제를 이분탐색으로 해결하고자 한다면

100이상의 수를 True, 아닌 수를 False로 하는 결정문제로 변환할 수 있습니다. 정답은 True중 가장 작은 수가 100이면 전체 답이 True입니다.

위의 결정 문제를 Data에 적용하면 결과는 모두 [False]가 됩니다. 

위에서 f(Low) != f(High)를 유지하며 반씩 쪼개며 탐색을 해야하지만, 모든 Data가 False이므로 어떻게 Low, High를 잡든 f(Low) = f(High)입니다. 이 경우 우리는 데이터에는 포함이 안되지만 High에 True가 있다고 가정을 합니다. 임의로 Dummy Data가 있다고 생각하는 거죠. 그렇지만 이것은 최종적으로 답을 구할 때는 고려되지 않습니다.

 

위와 같이 구현을 했다면 Low, High는 경계를 나눌 수 있도록 위치하게 됩니다. 

결정문제의 분포가 F~F|T~T일 때 정답이 가장 큰 F라면 Low를 가장 작은 T라면 High를 return 하면 됩니다.

 

제 설명보다 더 뛰어나고 대단한 제 스승님의 BOJ 블로그 글이 있습니다. 참고하시면 좋을 것 같습니다.

 

3. 추천 문제 list

각 문제에서 결정문제로 어떻게 바꿨는지, 최종 Low, High에서 답이 무엇인지에 집중해서 보면 좋을 것 같습니다.

BOJ 1920 수 찾기

 

1920번: 수 찾기

위의 예시 문제입니다.

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N = None
arr = None
M = None
query = None

def set_variable():
    global N, arr, M, query
    N = get_input()
    arr = sorted(list(get_line()))
    M = get_input()
    query = list(get_line())


def solution():
    def f(num):
        global N, arr, M, query
        L, R = -1, N
        while L + 1 < R :
            mid = (L + R) // 2
            if arr[mid] >= num : R = mid
            else : L = mid
        if (R != N and arr[R] == num) or (N == 1 and arr[0] == num ): return 1
        else : return 0
    
    for q in query:
        print(f(q))


if __name__ == "__main__":
    set_variable()
    solution()

 

BOJ 10816 숫자 카드 2

10816번: 숫자 카드 2

Python에서는 Dict를 이용해 해결해도 되지만.... C++의 Lower_Bound, Upper_Bound를 구현했습니다.

해당 문제는 X(num) 이상/초과(Lower_bound/Upper_Bound)이면 True 아니면 False로 했습니다. 이를 위해 입력 이후 정렬도 진행했습니다. 

결정 문제에서의 Data 예상 분포 [F, ..., F, T, ..., T]

문제의 탐색 범위를 -1 ~ N으로 지정해서, 주어진 전체 데이터보다 작은 경우도 큰 경우도 고려 가능하도록 탐색 범위를 지정했습니다.

Return시에는 R(High) 값을 Return 했습니다. 

Lower Bound를 예로 Lower Bound는 주어진 X(num)이상이면 True입니다. X이상이라면 X 데이터는 T중 최소값이므로 R(High)를 Return 해야합니다. 같은 맥락으로 Upper_Bound도 적용가능합니다.

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N, M = None, None
card = None
query = None

def set_variable():
    global N, M, card, query
    N = get_input()
    card = sorted(list(get_line()))
    M = get_input()
    query = list(get_line())


def solution():
    global query
    def lower_bound(L, R, num):
        global card
        while L + 1 < R:
            mid = (L + R) // 2
            if card[mid] >= num: R = mid
            else : L = mid
        return R # index pos

    def upper_bound(L, R, num):
        global card
        while L + 1 < R:
            mid = (L + R) // 2
            if card[mid] > num: R = mid
            else : L = mid
        return R # index pos
    
    for q in query:
        print(upper_bound(-1, N, q) - lower_bound(-1, N, q), end=" ")

if __name__ == "__main__":
    set_variable()
    solution()

 

BOJ 1654 랜선 자르기

1654번: 랜선 자르기

이 문제에서 K개의 랜선을 L이라는 길이로 잘랐을 때 N개의 길이의 랜선으로 잘릴 수 있는가?라는 결정문제로 바꾸면

길이 L에 대한 분포는 [True, ..., True, False, ..., False]가 됩니다.

이때 우리는 True의 최대값을 원하므로 Low를 Return 하면 됩니다.

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

K, N = None, None
arr = None

def set_variable():
    global K, N, arr
    K, N = get_line()
    arr = list()
    for _ in range(K):
        arr.append(get_input())
        

def solution():
    global K, N, arr
    def binary_search(L, R):
        def possible(num):
            cnt = 0
            for i in arr:
                cnt += (i // num)
            if cnt >= N : return True
            else : return False
        while L + 1 < R:
            mid = (L + R) // 2
            if possible(mid): L = mid
            else : R = mid
        return L
    
    print(binary_search(0, max(arr) + 1))
            


if __name__ == "__main__":
    set_variable()
    solution()

 

BOJ 2805번 나무 자르기

2805번: 나무 자르기

위 문제와 비슷합니다.

특정 길이 L로 나무를 잘랐을 때 남은 길이의 합이 M보다 크면 True, 아니면 False인 결정문제로 변환합니다.

길이 L에 대해서 분포가 [True, ..., True, False, ..., False]가 됩니다.

우리는 True의 최대값을 원하므로 Low를 return하면 됩니다.

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N, M = None, None
arr = None

def set_variable():
    global N, M, arr
    N, M = get_line()
    arr = list(get_line())

def solution():
    global N, M, arr
    def binary_search(L, R):
        def possible(num):
            length = 0
            for i in arr:
                length += 0 if i - num <= 0 else i - num
            if length >= M : return True
            else : False
        while L + 1 < R:
            mid = (L + R) // 2
            if possible(mid) : L = mid
            else : R = mid
        return L
    
    print(binary_search(0, max(arr) + 1))


if __name__ == "__main__":
    set_variable()
    solution()

 

BOJ 2110 공유기 설치

2110번: 공유기 설치

공유기 간 길이 L을 기준으로 C개 이상 설치 가능하면 True, 아니면 False인 결정문제로 변환합니다.

공유기 간 길이 L의 분포에 따른 정답의 분포는 [True, ..., True, False, ..., False]가 됩니다.

우리는 공유기 간 길이의 최대값을 알고 싶으므로 True의 최대값을 가지는 Low를 Return하면 됩니다.

import sys
import math

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N, C = None, None
pos = None

def set_variable():
    global N, C, pos
    N, C = get_line()
    pos = list()
    for _ in range(N):
        pos.append(get_input())
    pos.sort()


def solution():
    global N, C, pos
    def binary_search(L, R):
        def possible(dist): 
        # dist 보다 넓게 설치해서 C개 넘게 설치 할 수 있으면 True, 아니면 False
            pre_pos = -math.inf
            cnt = 0
            for i in pos:
                if i - pre_pos >= dist:
                    cnt += 1
                    pre_pos = i
                else: continue
            if cnt >= C : return True
            else : return False
        while L + 1 < R:
            mid = (L + R) // 2
            if possible(mid): L = mid
            else : R = mid
        return L
    print(binary_search(0, int(1e9+1)))


if __name__ == "__main__":
    set_variable()
    solution()

 

BOJ 1300 K번째 수

이 문제는 A[i][j] = i × j 임을 기억해야합니다.

A 배열 분포에 대해서 num 이상의 값은 True, 아니면 False인 결정 문제로 변환합니다.

위 결정문제를 A배열에 적용했을 때의 정답의 분포는 [False, .., False, True, ... , True]가 됩니다.

num 분포의 최소값을 원하므로 R(High)를 Return하면 됩니다.

다만, 문제는 A배열의 전체 원소의 갯수가 (10^5)^2 = 10^10개이므로 naive하게 구하면 안됩니다.

해당 테크닉은 코드를 통해 이해하시면 될 것 같습니다.

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N = None
K = None

def set_variable():
    global N, K
    N = get_input()
    K = get_input()


def solution():
    global N, K
    def binary_search(L, R):
        def possible(num):
            cnt = 0
            for i in range(1, N + 1):
                cnt += min(N, num // i)
            if cnt >= K : return True
            else : return False
        while L + 1 < R:
            mid = (L + R) // 2
            if possible(mid) : R = mid
            else : L = mid
        return R
    print(binary_search(0, int(1e9 + 1)))

if __name__ == "__main__":
    set_variable()
    solution()

 

BOJ 12015 가장 긴 증가하는 부분 수열 2

12015번: 가장 긴 증가하는 부분 수열 2

LIS를 O(N\logN)으로 구현 해야하는 문제입니다.

이분 탐색을 통해 LIS 배열의 내부 원소를 찾아 값을 갱신할 때 필요합니다.

import sys

get_line: iter = lambda: map(int, sys.stdin.readline().rstrip().split())
get_input: int = lambda: int(sys.stdin.readline().strip())

N = None
arr = None

def set_variable():
    global N, arr
    N = get_input()
    arr = list(get_line())


def solution():
    global N, arr
    def binary_search(arr, num):
        L, R = -1, len(arr)
        while L + 1 < R:
            mid = (L + R) // 2
            if arr[mid] >= num: R = mid
            else : L = mid
        return R

    LIS = list()
    for i in arr:
        if not LIS:
            LIS.append(i)
        elif LIS[-1] < i:
            LIS.append(i)
        else:
            LIS[binary_search(LIS, i)] = i
    print(len(LIS))

if __name__ == "__main__":
    set_variable()
    solution()