-
32. 이진 검색(Binary Search), 파이썬Python/파이썬 자료구조 알고리듬 2019. 6. 26. 19:07반응형
정렬된 데이터에서 검색할 때는 이진(이분) 검색이 더 효율적입니다.
친구가 1부터 100까지 숫자 중 하나를 고르고,
나는 그 숫자를 맞추는 게임을 한다고 가정합니다.친구는 "고른 숫자가 내가 제시한 숫자보다 크다, 작다, 맞다."를
대답해 줘야 합니다.이때 가장 빨리 정답을 찾는 법은
절반인 50을 제시하는 것입니다.여기서 친구가 작다고 하면
25를 불러보고...한번 검색할 때마다 절반이 날아갑니다.
엄청난 효율이죠.실제로 32라는 숫자를 찾아보겠습니다.
1. 50? 작아
2. 25? 커
3. 37? 작아
4. 31? 커
5. 34? 작아
6. 32? 정답6번 만에 찾을 수 있습니다.
from random import randint print("Guess the number!") secret_number = randint(1, 100) # print(f"The secret number is {secret_number}.") while True: try: guess = int(input("Please input your guess: ").strip()) except Exception as e: print(e) continue if guess < secret_number: print(f"{guess} is too small.") elif guess > secret_number: print(f"{guess} is too big.") else: print("You Win!") break이진 탐색 트리가 검색에 효과적이라는 이야기도 같은 원리입니다.
게다가 알고리듬이 쉬워 코딩도 쉽습니다. ~!
개념을 잡기 위해 간단하게 코딩해 보겠습니다.
(에러가 발생합니다.)def search(item, left, right): mid = (right + left) // 2 print(left, mid, right, end='? ') if mid < item: print('커') return search(item, mid, right) elif mid > item: print('작아') return search(item, left, mid) else: print('정답 =', mid) return True search(1, 1, 100) search(32, 1, 100) search(100, 1, 100) # 에러..1 50 100? 커 50 75 100? 커 75 87 100? 커 87 93 100? 커 93 96 100? 커 96 98 100? 커 98 99 100? 커 99 99 100? 커 99 99 100? 커 99 99 100? 커 . . . RecursionError: maximum recursion depth exceeded while calling a Python object이진 탐색 구현 시 자주 볼 수 있는 에러죠.
이런 에러를 off-by-one error 라고 합니다.(left ~ mid) 검사 영역과 (mid~right) 검사 영역이
겹치지 않고, 둘이 합쳐서 전체 영역을 커버해야
이 문제를 해결할 수 있습니다.위 코드를 보면 1~50을 검사했음에도 불구하고,
다음 검사에는 50~100을 검사합니다.이렇게 생각해도 됩니다.
올릴 때 1 만큼 더 올려주고 (min = mid + 1)
내릴 때 1 만큼 더 낮춰주면 해결됩니다. (max = mid - 1)인심 팍팍def search(item, left, right): mid = (right + left) // 2 print(left, mid, right, end='? ') if mid < item: print('커') return search(item, mid + 1, right) elif mid > item: print('작아') return search(item, left, mid - 1) else: print('정답 =', mid) return True search(100, 1, 100)1 50 100? 커 51 75 100? 커 76 88 100? 커 89 94 100? 커 95 97 100? 커 98 99 100? 커 100 100 100? 정답 = 100실제 프로젝트에선 재귀를 쓰지 않는 것이 좋다고 했습니다.
재귀를 쓰지 않는다면 이렇게도 코딩할 수 있을 것입니다.def search(item, left, right): mid = (right + left) // 2 while mid != item: mid = (right + left) // 2 print(mid, end='? ') if mid < item: print('커') left = mid + 1 elif mid > item: print('작아') right = mid - 1 print('정답 =', mid) return True search(1, 1, 100) search(32, 1, 100) search(100, 1, 100)이진 탐색을 확장한 파라메트릭 서치라는 것도 있습니다.
아래 블로그 설명이 너무 좋아서...https://sarah950716.tistory.com/16
[이분탐색] 파라메트릭 서치(개념)
파라메트릭 서치 문제는 단독 문제로 나오기보다는 다른 알고리즘과 결합해서 출제되는 것 같습니다.파라메트릭 서치는 간단히 말하자면, (갓종만북의 표현을 빌려) 최적화 문제(문제의 상황을
sarah950716.tistory.com
이진 검색을 이용한 문제를 풀어봅시다.
입국 심사 :
https://comdoc.tistory.com/entry/%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC금과 은 운반하기:
https://comdoc.tistory.com/entry/%EA%B8%88%EA%B3%BC-%EC%9D%80-%EC%9A%B4%EB%B0%98%ED%95%98%EA%B8%B0징검다리 건너기:
https://comdoc.tistory.com/entry/징검다리-건너기※ bisect
https://docs.python.org/ko/dev/library/bisect.html파이썬에는 bisect라는 내장 모듈이 있습니다.
(bisect란 양분하다는 뜻입니다.)이 모듈은 정렬된 리스트에 요소를 삽입할 때
이진 검색 알고리듬을 사용해
순서에 맞는 위치를 찾아 삽입해 줍니다.정렬 상태가 유지됩니다.
bisect.bisect 함수를 먼저 설명하겠습니다.
삽입할 위치를 찾는 함수입니다.
찾는 숫자와 같은 숫자가 리스트 내에 있을 때
그 숫자의 왼쪽에 삽입할지 오른쪽에 삽입할지 정해야겠죠?그것까지 결정할 수 있습니다.
bisect.bisect_left(a, x, lo=0, hi=len(a)) bisect.bisect_right(a, x, lo=0, hi=len(a))bisect.bisect 는 오른쪽 위치를 반환합니다.
실제로 삽입할 때는 bisect.insort를 사용합니다.
삽입이라는 뜻의 insert에 sort의 의미를 추가하여 insort라고 재미있게 변형했네요. ^^
bisect.insort_left(a, x, lo=0, hi=len(a)) bisect.insort_right(a, x, lo=0, hi=len(a)) bisect.insort(a, x, lo=0, hi=len(a))학점을 매길 때 유용합니다.
>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'): ... i = bisect(breakpoints, score) ... return grades[i] ... >>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]] ['F', 'A', 'C', 'C', 'B', 'A', 'A']bisect와 heapq(https://comdoc.tistory.com/entry/파이썬의-heapq-모듈)가 거의 비슷합니다. 비교해 보시길..
반응형