사용자 도구

사이트 도구


ps:이진_검색

이진 검색 (Binary search)

  • 이분 탐색이라고 배웠던 것 같은데, 한국어 위키에는 이진 검색으로 되어있다.
    • 구글에서 검색해서 나온 문서수를 비교하면 이진»이분이고, 검색이냐 탐색이냐 싸움이네..
      • 이진 검색: 34,300
      • 이분 검색: 9,150
      • 이진 탐색: 42,100
      • 이분 탐색: 16,700
      • 바이너리 서치; 3,730
  • 루프로 구현해도 별로 어렵지 않아서, 굳이 재귀로 구현할 필요가 없다.
  • Python에서는 bisect 모듈에 순수 파이썬으로 구현되어 있으니 이걸 쓰면 된다. 코드도 매우 짧다
    • 다만 함수 이름이나 사용법이 약간 비직관적이어서, 매뉴얼에 흔한 사용예들을 추가해줬다

파라메트릭 서치

  • 이진검색의 응용? 일반화?
  • 대충 비교하면
    • 이진검색 - 정렬된 배열 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를 찾는 문제로 바꿔 표현함으로서, 파라메트릭 서치를 적용할 수 있다.

관련 문제

코드

토론

댓글을 입력하세요:
U J H A G
 
ps/이진_검색.txt · 마지막으로 수정됨: 2021/01/21 05:55 저자 teferi