이진 검색 (Binary search)

• 이분 탐색이라고 배웠던 것 같은데, 한국어 위키에는 이진 검색으로 되어있다.
  • 뭐가 제일 대중적인 번역인지 구글에서 검색해서 나온 문서수를 비교하면 이진»이분이고, 검색이냐 탐색이냐 싸움이네..
    • 이진 검색: 34,300
    • 이분 검색: 9,150
    • 이진 탐색: 42,100
    • 이분 탐색: 16,700
    • 바이너리 서치; 3,730
  • binary search tree 를 번역할때는 '이분'대신 '이진'을 쓰는게 훨씬 자연스러운 점을 고려하면, 여기서도 '이진'이 더 적절한거 같은데 입에 안붙기는 한다..
• 기본 개념은 https://en.wikipedia.org/wiki/Binary_search_algorithm 참고

• 이진 검색을 일반화시킨 개념이라고 생각할수 있다.
• 사실 국내 커뮤니티들에서는 아래에서 설명할 이진검색의 일반화된 활용을 파라메트릭 서치라고 흔히 사용되지만, 외국에서는 그렇지 않다. 파라메트릭 서치는 최적화 문제를 결정 문제로 바꿔서 푸는 기법을 말하는게 맞긴 하지만, 이진검색을 이용한 풀이는 이렇게 부르는 경우는 찾지 못했다. 그냥 이진 검색.. 또는 binary search on monotonic function 정도로 부르는것을 본적 있다.
  • 하지만, 국내에서는 대충 파라메트릭 서치 하면 이걸 의미하니까 그냥 이렇게 부르겠다.
• 대충 비교하면
  • 이진검색 - 정렬된 배열 a의 원소들 중에서 a[i]>=x 인 최소의 i를 찾는다
  • 파라메트릭 써치 - [beg,end)의 자연수들 중에서 f(x)를 만족시키는 최소의 x를 찾는다.
• 기본적인 사용법은 최소값이나 최대값을 찾는 최적화 문제를 결정 문제로 바꾸어서 파라메트릭 써치로 푸는 것이다.
  • f(x)가 true가 되는 최소의 x를 찾는 문제는 풀기 어렵지만, 특정 x에 대해서 f(x)가 true인지를 구하는 것은 쉬운 상황을 생각하자. 가능한 범위 안의 모든 x에 대해서 f(x)를 계산해보면, 이중에서 f(x)가 true가 되는 최소의 x를 찾는것은 당연히 가능하다. 그리고, 만약 f(x)가 어떤 t를 기준으로 x⇐t 일때는 false이고, x>t이면 true 라면, 그 t를 찾는 것은 이분탐색으로 찾을 수 있고, 이것이 파라메트릭 서치이다.
• 좀 더 활용하면, f(x)가 단조증가인 경우, f(x)=b가 되는 x를 찾는 문제도 f(x)>=b가 되는 최소의 x를 찾는 문제로 바꿔 표현함으로서, 파라메트릭 서치를 적용할 수 있다.
• 다음은 기억해두면 유용한 유형들.
  • 어떤 시퀀스에서 k번째 수를 찾는 문제. 시퀀스에서 x보다 작거나 같은 수의 갯수를 빠르게 셀수 있다면, x보다 작거나 같은 숫자의 갯수가 k개인 x의 최솟값을 이진탐색으로 찾는 식으로 풀 수 있다

• 개념이 간단한 것과는 달리, 구현은 상당히 까다롭다 (실수하기 쉽다)
  • 나 혼자 생각이 아니라, 무려 크누스도 인정한 부분이다..
    • <blockquote>Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky</blockquote>
• 구현과정에서 세부 디테일을 잡을수 있는 방법이 몇종류가 있는데, 이 방식들이 서로 섞여서 헷갈리지 않아야 한다.
  • 위키에서도 비슷하지만 사소하게 다른 두가지 구현을 소개한다.
  • 백준 블로그에도 이분 탐색(Binary Search) 헷갈리지 않게 구현하기 라는 글이 올라와있으니 참고
• 흔히 쓰이는 탐색 범위를 절반씩 줄여가면서 구현하는 방법 외에도, 바이너리 점핑을 이용한 구현도 존재한다. 예시 - USACO guide. 앞에 구현보다 헷갈릴 여지가 적다는 것이 장점이다
  • 관리해야할 변수가 lo,hi 두개에서, dif 하나로 줄어들었다는 차이도 있는데, 병렬 이분 탐색 (Parallel Binary Search; PBS)을 구현할때는 이점이 꽤 도움된다.
• 파라메트릭 서치가 아닌, 그냥 정렬된 리스트에서 특정 원소를 찾는 함수는 bisect 모듈에 이미 구현되어 있다.
  • 다만 함수 이름이나 사용법이 약간 비직관적이어서, 매뉴얼에 있는 흔한 사용예들을 참고하자
• 하지만 파라메트릭 서치 문제에서는 bisect 모듈을 사용할수 없고, 매번 직접 구현하기에는 코드는 길지 않지만 실수하기 쉬운 요소들이 많으므로, teflib에 구현체를 만들어서 사용했었다
• 처음 버전은 teflib.algorithm.binary_search으로, [beg,end)의 자연수들 중에서 f(x)를 만족시키는 최소의 x를 찾는 함수이다. 만약 f(x) 를 만족시키는 최대의 x를 찾아야 하는 경우에는 인자로 not f(x) 를 넘겨주고 결과에서 1을 빼주는 형식으로 사용하면 굳이 두종류의 함수를 따로 만들 필요가 없었다.
• 그러나 not f()를 넘기고, 결과에서 1을 빼서 사용하는 것 조차도 용법을 종종 까먹고 불편해져서, 그냥 최소 x를 찾는 함수와, 최대 x를 찾는 함수를 나눠서 만들기로 했고, 함수 이름도 maximum_valid_integer 와 minimum_valid_integer로 바꿨다.
  • teflib.binsearch.maximum_valid_integer
  • teflib.binsearch.minimum_valid_integer
• 하지만.. 파라메트릭 서치조차도 bisect모듈을 사용해서 처리할수 있다는 것을 깨달았다! 자세한 내용은 아래 섹션에.

• 시작은, python 3.10부터는 bisect.bisect_left 함수에서 key 인자를 받을수 있게 되었다는 것을 알게 되면서였다. 그러면 f를 key로 넘겨주면 그냥 bisect 모듈을 그냥 써서 할수 있는 것 아닌가??
• 하지만, bisect 모듈의 함수는 인자로 여전히 시퀀스를 받는다는 문제가 있다. 1억까지 범위에서 답을 찾기 위해서 길이가 1억인 리스트를 만들어서 넘겨줄수는 없지 않는가..
• 음.. 근데 해결 못할것도 아닌데? 굳이 진짜 리스트를 만들어서 넘겨줘야 하나? 그냥 리스트-like한 클래스를 만들어서 그 인스턴트를 넘겨주면 되는거 아님?? 실제 라이브러리 코드에서는 []을 이용한 인덱싱 외에는 다른 메소드를 아예 안쓰는거 같은데 그러면 __getitem__만 오버라이딩해주면 되는거 아님??

  • # 이런 클래스를 만들면..
    class MySeq:
        def __getitem__(self, x):
            return x 
    
    def f(x: int) -> bool:
      ...
      
    def g(x: int) -> int
      ...
    
    # 그냥 이렇게 쓸수 있잖아?
    answer = bisect.bisect_left(MySeq(), x, lo, hi)  # [lo,hi] 에서 x를 찾기
    answer = bisect.bisect_left(MySeq(), 1, lo, hi, key=f)  # [lo,hi] 에서 f(x)가 True인 최소의 x를 찾기 
    answer = bisect.bisect_left(MySeq(), b, lo, hi, key=g)  # [lo,hi] 에서 g(x)>=b인 최소의 x를 찾기

    • getitem을 오버라이딩하는 부분은 조금 언급이 필요하다. 클래스를 따로 만들기조차 귀찮으니까 그냥 인스턴스 자체에서 오버라이딩을 시켜버리면 더 편할것 같은데, 파이썬 문법적으로 그것은 불가능하다. https://docs.python.org/3/reference/datamodel.html#special-method-lookup 참고. 스택오버플로우에도 좀더 자세한 설명이 있다.
      • type() 로 클래스 자체를 다이나믹하게 선언해서 사용하는 방법은 가능하기는 하다..
• 거기에다가 조금 더 생각해보니.. 굳이 코드를 저렇게 getitem 이 인덱스를 그대로 리턴해주면 그 값을 f에 넣어서 구할 필요 없이, 그냥 getitem이 f값을 계산해서 리턴하도록 해버리면 된다는 것을 떠올렸다!!!

  • def g(x: int) -> int
      ...
    
    class G:
        def __getitem__(self, x):
            return g(x) 
      
    answer = bisect.bisect_left(G(), b, lo, hi)  # [lo,hi] 에서 g(x)>=b인 최소의 x를 찾기

  • 와우 이거 좀 쩔지 않음???
  • 이렇게 하면 key 인자를 안쓰니까, 굳이 python 3.10 이상이 필요하지도 않다
• 이제 더이상 파라메트릭 서치든 뭐든 이진검색을 직접 구현할 필요가 없게 되었다. teflib에서의 관련 함수는 다 deprecate시켜버리고 이제 모든 경우에 bisect를 사용하자!
• 다만 이렇게 한다고 속도가 빨라지지는 않는다. 보통은 시간이 걸리는 함수를 pure python으로 구현한 것을 c로 구현된 내부 라이브러리를 쓰도록 바꾸면 큰 속도 향상이 따르는데.. 이진검색같은 경우는 이부분에서 시간이 지체되는 경우가 거의 없으니까.. (반복 횟수가 탐색범위의 로그값만큼만이므로, 탐색 범위가 2^64 라고 해봤자 64번밖에 안돌아간다)속도에는 별 차이가 없다.
• f(x) 가 True인 최대의 x를 찾는 문제.. 즉, x⇐t 에서는 True이고, x>t 에서는 False가 인 경우의 t를 찾는 문제는 다시 좀 귀찮아지기는 한다. getitem의 결과값은 항상 단조증가해야만 로직이 돌아가므로.. 결국 예전처럼 결국 not f(x)를 리턴해야 하고, 찾아진 값에서 1을 빼서 쓰는 방법으로 구현해야 한다..
  • 뭐.. 이렇게 하자면 못쓸 이유는 없는데.. 나중에 갑자기 쓰려면 또 헷갈릴것 같단 말이지…
• 고민끝에 별로 마음에는 안들지만 그냥 teflib.binsearch 를 다시 살려놓기로 했다… 뜬금 getitem을 오버라이드한 클래스가 코드 중에 튀어나오는 것보다는 이렇게 한번 함수로 래핑하는 것이 가독성면에서도 낫겠지 하는 생각이었다

[업데이트]

• 기존 teflib의 구현체는, 앞에서 설명한 방법을 적용해서 이런식으로 구현되어있었다,.

  • def minimum_valid_integer(
        beg: int, end: int, is_valid_func: Callable[[int], bool]
    ) -> int:
        seq = type('X', (), {'__getitem__': lambda self, x: is_valid_func(x)})()
        return bisect.bisect_left(seq, True, beg, end - 1)

• 사실 1년 이상 이 코드를 쓰면서 문제를 찾지 못했다. 이분 탐색으로 답을 찾는 코드에서, 이분탐색 함수를 실행시키는 횟수는 보통 한번이고, 여러번 실행되는 것은 predicate 함수니까, 이분탐색 함수의 실행이 느려도 거의 차이를 못느꼈다.
• 하지만, 이분탐색 함수를 여러번 실행해야 하는 문제를 풀다가, 위의 코드를 반복 수행하면 속도가 느려진다는 것을 알게 되었다. 그리고 그 느려지는 정도가 CPython보다 Pypy에서는 매우 심각하게 나타난다는 것을 알게 되었다…
• 위 함수를 여러번 실행해서 풀어야 하는 문제가 있다. 이진탐색 구현을 바꿔가면서 제출해서 성능을 비교해봤다

• binary_search는 그냥 Seq클래스나 bisect모듈 따위를 사용하지 않고 평범하게 pure python 으로 구현한 이진 탐색 함수이다. 가장 빨랐다.

  • def binary_search(beg, end, predicate):
        while beg < end:
            mid = (beg + end) >> 1
            if predicate(mid):
                end = mid
            else:
                beg = mid + 1
        return beg

• minimum_valid_integer는 binary_search에 비해서 느렸다. 다만 느린 정도가, CPython은 2배 이내인데, Pypy는 15배 이상 느려졌다
• minimum_valid_integer2 는 minimum_valid_integer에서 매번 동적으로 클래스를 생성하고, 클래스의 인스턴스를 생성하는 것이 문제의 원인이라 생각해서, 클래스를 외부에서 정적으로 선언하고, 함수 안에서는 인스턴스만 생성하게 바꾼 버전이다. 속도가 정상적으로 줄어든걸로 보아서, 동적 클래스의 생성이 pypy에서 문제가 된 것이 맞았던것 같다

  • class Seq:
        def __init__(self, is_valid_func):
            self._is_valid_func = is_valid_func
    
        def __getitem__(self, x):
            return self._is_valid_func(x)
    
    
    def minimum_valid_integer2(
        beg: int, end: int, is_valid_func: Callable[[int], bool]
    ) -> int:
        return bisect.bisect_left(Seq(is_valid_func), True, beg, end - 1)

• minimum_valid_integer3 은 함수에서 매번 인스턴스를 생성하는것도 마음에 들지 않아서, 인스턴스를 전역 변수로 만들어두고, bisect 의 key로 predicate을 넘기는 방식이다. 속도는 비슷했다.

  • _SEQ = type('_X', (), {'__getitem__': lambda self, x: x})()
    
    
    def minimum_valid_integer3(
        beg: int, end: int, is_valid_func: Callable[[int], bool]
    ) -> int:
        return bisect.bisect_left(_SEQ, True, beg, end - 1, key=is_valid_func)

• 일단 minimum_valid_integer 의 구현은 바꾸기는 바꿔야 할것 같다. 그럼 뭘로 바꿀것인가.
  • 속도 면에서는 그냥 pure python으로 새로 짠 binary_search를 쓰는 것이 제일 빠르다.
  • 코드를 컴팩트하게 하기 위해서는 minimum_valid_integer3 이 제일 간결하다
  • 음.. 그냥 binary_search를 쓸까.?

• 어떤 아이템들을 골고루 분배하는 방법을 찾기
  • 여기에서 골고루라는 것은 '최댓값을 최소화'시키거나 '최솟값을 최대화'시키는 방법을 말한다. 이때의 문제는 그때의 최댓값이나 최솟값을 찾는것이 된다.
  • 이때의 결정문제는 '아이템들을 모두 합이 X이하/이상이 되는 그룹들로 묶을수 있는가' 가 될텐데, 이것은 대부분 단순히 그리디하게 시뮬레이션 해보면 가능 여부를 확인할수 있다. 앞에서부터 합이 X에 최대한 가깝도록 묶어봐서, 모두 다 묶을수 있으면 된다.
  • 관련 문제
    • 공유기 설치 : 최솟값을 최대화시키면서 전체 구간을 X개의 구간으로 나누기
    • 군수품 창고 정리 : 최댓값을 최소화시키면서 전체 아이템을 X개의 그룹으로 나누기

• teflib.binsearch.maximum_valid_integer
• teflib.binsearch.minimum_valid_integer

• 기본 컨셉은 동일하다. 결정함수가 실수를 받아서 처리하게 되고, 실수의 특성상 정확한 값을 찾는 대신 오차 범위 이내의 값을 찾도록 문제가 주어진다.
• 탐색 범위를 실수 범위로 줄여나가면서 탐색하면 된다. hi-lo가 오차범위 이내로 줄어들면 멈추게 된다. 어차피 오차를 가정하고 답을 구하기 때문에, 정수 범위에서 처리할때처럼 off-by-one 에러에 신경을 덜 써도 된다. <와 ≤중 뭘 써야 하는지 매번 헷갈리던 것에서 벗어날수 있다는 것은 좋은 점이다
• 하지만, off-by-one 에러 대신에 신경써야 할 부분이 있는데, 정답의 자릿수가 큰 경우에는, 반복횟수가 어느정도 넘어가면 hi-lo가 더 이상 줄어들지 않을 수 있다. 이는 c++기준으로는 실수 자료형을 double 대신 float으로 사용했을때 흔히 발생하지만, double를 사용하더라도 자릿수가 커지면 발생할수 있다. python도 마찬가지. 이렇게 되면 아무리 반복해도 hi-lo가 오차범위 이내로 줄어들지 않기 때문에 무한 루프를 타게 된다. 이것을 방지하기 위해 흔히 사용하는 방법은, 반복횟수의 상한을 정해놓는 것이다. 보통 100번이나 200번을 상한으로 잡는다.
• 관련 문제
  • 1166
  • 2022
  • Marathon

• Stern-Brocot Tree 를 이용해서 처리할수 있다.