#15 이분 탐색(Binary Search)

 이분 탐색은 N개의 데이터의 탐색을 로그시간으로 완료할 수 있어 코딩 테스트에서 시간복잡도를 개선하는데 굉장히 자주 사용되는 알고리즘이다.  이번에는 이분탐색을 활용하여 풀 수 있는 몇 가지 문제들을 살펴본다. 

 

1. 랜선 자르기(https://www.acmicpc.net/problem/1654)

 k개의 랜선의 길이와 필요한 랜선의 갯수 n이 주어졌을 때,  같은 길이의 n개의 랜선을 만들 수 있는 랜선의 최대길이를 구하는 문제이다. 해결하는 절차와 이를 구현한 코드는 다음과 같다.

 

① 랜선을 m만큼의 길이로 자른다고 가정한다.

② 길이는 정수이며 0으로 자르는것은 의미가 없기 때문에 m의 최솟값은 1이 된다.

③ k개의 랜선을 손실을 최소화하여 잘라도 n개의 선을 만들기 위해서는 m은 랜선의 길이를 모두 합한 값을

    n으로 나눈 것 보다 작거나 같기 때문에 m의 최댓값은 sum(lans) // n이 된다.

④ 1이상 sum(lans) // n 이하의 정수에서 이분탐색을 실시한다

⑤ 만약 랜선을 m만큼씩 잘랐을 때 n개보다 적다면 더 작게 잘라서 수를 늘리기 위해 e = m - 1

⑥ 만약 랜선을 m만큼씩 잘랐을 때 n개 이상이라면 최댓값을 찾기 위해 s = m + 1

⑦ 탐색이 종료된 시점에서 s는 마지막으로 n개의 랜선을 만드는데 성공한 m에 1을 더한 값이므로 문제의 답은 s -1

 

import sys

input = sys.stdin.read


def sol1654():
    k, n, *lans = map(int, input().split())
    
    # 2, 3
    s, e = 1, sum(lans)//n
    
    # 4
    while s <= e:
    	# 1
        m = (s + e) // 2
        # 5
        if sum([lan//m for lan in lans]) < n:
            e = m - 1
        # 6
        else:
            s = m + 1
    # 7
    return s-1

이런 식으로 이분 탐색을 활용하여 어떤 조건을 만족하는 최소/최대 값을 찾는 방식을 parametric search라고 한다.  최소/최대값을 찾으려는 값의 범위내에서 이분탐색을 실행하여 중간값에 대하여 조건의 만족여부를 검사한 뒤 조건을 만족한다면 좀더 최적의 값을 찾아내기 위한 방향으로 범위를 좁히고, 조건을 만족하지 못한다면 조건을 만족할 수 있는 방향으로 범위를 좁혀나가며 최적의 값을 탐색하는 것이다.  같은 방식이지만 좀더 어려운 문제로 백준의 1300번 문제(https://www.acmicpc.net/problem/1300)가 있지만 parametric search를 활용한다는 것만 염두에 두면 쉽게 해결 가능한 문제이니 따로 다루지는 않는다.

 

 

2. 가장 긴 증가하는 부부 수열 2(https://www.acmicpc.net/problem/12015)

수열 A의 크기 N과 수열 A가 주어졌을 때 가장 긴 증가하는 부분수열의 길이를 구하는 문제이다. 랜선 자르기 문제의 경우 문제 해결의 핵심이 이분탐색의 응용이었다면 이 문제에서는 문제를 해결하기 위한 알고리즘(LIS 알고리즘)을 최적화하기 위한 수단으로 사용된다.  문제를 해결하는 절차와 이를 구현한 코드는 다음과 같다.

 

① 비어있는 배열(리스트) lis 를 생성

② A의 원소 a에 순차적으로 접근

③ 만약 lis가 비어있거나 a가 lis의 마지막 값보다 크다면 증가수열의 길이가 늘어난 것으로 볼 수 있기에

    lis에 a를 append

④ 그렇지 않다면 이 수를 포함한 증가하는 부분 수열이 길이가 가장 길 수도 있기 때문에 lis 내의 원소 중에서

    a보다 크거나 같은 수 중에서 가장 작은 수를 대체

⑤ A의 순회가 끝난 후 lis의 길이가 최장 증가 수열의 길이가 된다.

 

import sys

input = sys.stdin.read


def sol12015():
    n, f, *seq = map(int, input().split())
    
    # 1
    lis = [f]
    
    # 2
    for num in seq:
    	# 3
        if num > lis[-1]:
            lis.append(num)
        # 4
        else:
            s, e = 0, len(lis)-1
            while s <= e:
                m = (s + e) // 2
                if lis[m] < num:
                    s = m + 1
                else:
                    e = m - 1
            lis[e+1] = num
    # 5
    return len(lis)

이 풀이의 4번 과정에서, 오름차순 정렬된 배열 lis에서 num 보다 크거나 같은 수 중 최솟값의 위치를 찾기 위해 이분탐색이 활용된 것을 볼 수 있다.  이분 탐색의 응용이긴 해도 parametric search의 형태였던 1번 문제와는 달리 여기서의 이분탐색은 정렬된 배열에 대해 실시하는 일반적인 이분 탐색이다.  

 

 

3. bisect 모듈

2번 문제를 직접 구현한 이분 탐색으로 풀 경우 시간초과는 발생하지 않지만 상당히 느리다. 또한 이분탐색의 구현이 어려운 편은 아니지만 이분 탐색이 필요할 때 마다 매번 직접 구현하는 것은 꽤나 귀찮고 시간을 잡아먹는 일이다. 파이썬에서는 bisect 모듈을 사용하여 직접 구현할 필요 없이 이분탐색을 실시할 수 있다. 

 

import sys
# bisect 모듈의 bisect_left 함수 import
from bisect import bisect_left

input = sys.stdin.read


def sol12015():
    n, f, *seq = map(int, input().split())
    lis = [f]
    for num in seq:
        if num > lis[-1]:
            lis.append(num)
        # lis에서 num이 들어갈 자리를 탐색
        else:
            lis[bisect_left(lis, num)] = num
    return len(lis)

bisect 모듈의 bisect_left, bisect_right 는 탐색할 리스트와 키가 될 값을 입력받아 해당 값을 리스트가 정렬된 상태를 유지하며 삽입하기 위한 인덱스를 반환한다.  배열에 키 값과 중복되는 값이 존재할 경우, bisect_left는 중복 값중 가장 앞쪽에 있는 값의 인덱스를 반환하며, bisect_right는 키 값보다 큰 값중 최솟값의 인덱스를 반환한다는 것이다.  여기서는 num 보다 크거나 같은 값중 최솟값을 찾아야 하기에 bisect_left를 사용하였다.  

 

위쪽이 bisect 모듈을 사용한 코드, 아래쪽은 직접 이분탐색을 구현 한 코드를 제출한 것이다.

bisect 모듈을 사용하면 코드 작성의 시간도 절약하고 편리할 뿐만 아니라 퍼포먼스 상에서도 이점이 있다.  탐색할 배열의 크기가 커질수록 bisect 모듈을 사용한 탐색이 대체로 더 좋은 성능을 보인다.