사용자 도구

사이트 도구


ps:이진_검색

이진 검색 (Binary search)

  • 이분 탐색이라고 배웠던 것 같은데, 한국어 위키에는 이진 검색으로 되어있다.
    • 뭐가 제일 대중적인 번역인지 구글에서 검색해서 나온 문서수를 비교하면 이진»이분이고, 검색이냐 탐색이냐 싸움이네..
      • 이진 검색: 34,300
      • 이분 검색: 9,150
      • 이진 탐색: 42,100
      • 이분 탐색: 16,700
      • 바이너리 서치; 3,730

파라메트릭 서치

  • 이진검색을 일반화시킨 개념이라고 생각할수 있다.
  • 사실 국내 커뮤니티들에서는 아래에서 설명할 이진검색의 일반화된 활용을 파라메트릭 서치라고 흔히 사용되지만, 외국에서는 그렇지 않다. 파라메트릭 서치는 최적화 문제를 결정 문제로 바꿔서 푸는 기법을 말하는게 맞긴 하지만, 이진검색을 이용한 풀이는 이렇게 부르는 경우는 찾지 못했다. 그냥 이진 검색.. 또는 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>
  • 구현과정에서 세부 디테일을 잡을수 있는 방법이 몇종류가 있는데, 이 방식들이 서로 섞여서 헷갈리지 않아야 한다.
  • 흔히 쓰이는 탐색 범위를 절반씩 줄여가면서 구현하는 방법 외에도, 바이너리 점핑을 이용한 구현도 존재한다. 예시 - USACO guide. 앞에 구현보다 헷갈릴 여지가 적다는 것이 장점이라는데 실제로 구현해보지는 않았다..
  • 파라메트릭 서치가 아닌, 그냥 정렬된 리스트에서 특정 원소를 찾는 함수는 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로 바꿨다.
  • 하지만.. 파라메트릭 서치조차도 bisect모듈을 사용해서 처리할수 있다는 것을 깨달았다! 자세한 내용은 아래 섹션에.

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을 오버라이드한 클래스가 코드 중에 튀어나오는 것보다는 이렇게 한번 함수로 래핑하는 것이 가독성면에서도 낫겠지 하는 위안을 가져본다..

관련 문제

구현

토론

댓글을 입력하세요:
F D N​ E E
 
ps/이진_검색.txt · 마지막으로 수정됨: 2022/04/22 05:44 저자 teferi