들어가면서
브루트 포스의 단점이 방대한 input에서는 성능이 떨어진다는 점이였습니다. 이를 해결할 수 있는 게 “이분 탐색” 입니다. 말 그대로 반으로 나누어 탐색하는 거죠 ㅎㅎ
어떻게 반으로 나누어서 탐색하는 데 답을 찾을 수 있을까요?
이번 포스트에서는 “이분 탐색”에 대해서 공부한 내용을 정리해보겠습니다.
이분 탐색 개념
이분 검색은 정렬된 배열 또는 리스트 내에서 대상 값을 효율적으로 찾는 데 사용되는 기본 알고리즘 기술입니다.
이분 탐색의 핵심 아이디어는 목표 값이 발견되거나 존재하지 않는 것으로 판단될 때까지 탐색 간격을 반복적으로 반으로 나누는 것입니다.
아래는 이분 탐색을 가장 쉽게 표현한 그림이 있어서 가져온 그림입니다 ㅎㅎ
37을 찾고자 할 때, 이분 탐색은 3번의 탐색만으로 원하는 수를 찾았고, 완전 탐색의 경우 더 많은 탐색이 필요하다는 것을 잘 보여주고 있습니다.
이분 탐색 방법
- 전체 정렬된 배열 또는 리스트로 시작합니다.
- 목표 값을 배열의 중간 요소와 비교합니다.
- 대상 값이 중간 요소와 일치하면 검색이 완료됩니다.
- 대상 값이 중간 요소보다 작으면 배열의 아래쪽 절반에서 검색을 계속합니다.
- 대상 값이 중간 요소보다 크면 배열의 위쪽 절반에서 검색을 계속합니다.
- 목표 값을 찾거나 검색 간격이 비어 있을 때까지 2-5단계를 반복합니다.
파이썬으로 이분 탐색 구현
반복문으로 이분 탐색
# 반복문으로 구현한 이진 탐색
def iter_binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
# 원하는 값 찾은 경우 인덱스 반환
if array[mid] == target:
return mid
# 원하는 값이 찾은 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
elif array[mid] > target:
end = mid - 1
# 원하는 값이 찾은 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
else:
start = mid + 1
return None재귀 함수로 이분 탐색
# 재귀 함수로 구현한 이진 탐색
def recursive_binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
# 원하는 값 찾은 경우 인덱스 반환
if array[mid] == target:
return mid
# 원하는 값이 찾은 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
elif array[mid] > target:
return recursive_binary_search(array, target, start, mid - 1)
# 원하는 값이 찾은 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
else:
return recursive_binary_search(array, target, mid + 1, end)
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = recursive_binary_search(array, target, 0, n - 1)
if result is None:
print('원소가 존재 하지 않음')
else:
print(result + 1)이분 탐색 문제
수 찾기 문제는 백준 1920번으로 아래와 같습니다.
해당 문제는 밑에 링크를 타고 들어갈 수 있습니다.
이 문제를 이진 탐색이 아니라 브루트 포스로 풀 수도 있습니다.
하지만 input을 10만까지 입력 받기 때문에 완전 탐색으로 풀 경우 시간 초과가 걸립니다…
sys.stdin.readline(), sys.stdout.write() 란??
위 문제를 이진 탐색이 아니라 아래와 같은 완전 탐색으로 풀면 시간 초과가 발생합니다.
sys.stdin.readline(), sys.stdout.write()는 input()과 print()를 빠르게 하기 위한 방법입니다
아래 글 참고
import sys
present_num = int(sys.stdin.readline())
present_nums = list(map(int, sys.stdin.readline().split()))
find_num = int(sys.stdin.readline())
find_nums = list(map(int, sys.stdin.readline().split()))
for target in find_nums:
sys.stdout.write('1\n' if target in present_nums else '0\n')import sys
present_num = int(sys.stdin.readline())
present_nums = list(map(int, sys.stdin.readline().split()))
find_num = int(sys.stdin.readline())
find_nums = list(map(int, sys.stdin.readline().split()))
for target in find_nums:
sys.stdout.write('1\n' if target in present_nums else '0\n')
위의 문제를 이진 탐색으로 아래와 같이 풀면 시간 복잡도를 줄여서 해결 할 수 있습니다.
import sys
present_num = int(sys.stdin.readline())
present_nums = sorted(list(map(int, sys.stdin.readline().split())))
find_num = int(sys.stdin.readline())
find_nums = list(map(int, sys.stdin.readline().split()))
def iter_binary_search(target):
start, end = 0, present_num-1
while start <= end:
mid = (start+end)//2
if present_nums[mid] == target:
sys.stdout.write("1\n")
return
elif target > present_nums[mid]:
start = mid + 1
else:
end = mid - 1
sys.stdout.write("0\n")
for target in find_nums:
iter_binary_search(target)물론 다른 좋은 방법들도 있으나 오늘은 이분 탐색 정리시간이니 이분 탐색으로 푸는 방법만….ㅎㅎ
이분 탐색으로 풀 수 다른 문제도 아래와 같이 있습니다 ㅎㅎ
마치며
이진 탐색을 이해 하더라도 구현 단계에서 오류가 많이 발생했습니다.
제가 구현하면서 발생했던 오류들을 정리해보면서 마치겠습니다.
중단점 설정
아주 처음에는 이진 탐색의 중단점을 찾는 게 어려웠습니다. 하지만 다시 생각해보니 굉장히 단순한 중단 조건이네요…
첫번째 중단점 : 찾는 값이 없는 경우인데요
이분 탐색은 탐색하는 start, end 범위를 계속 바꿔가면서 탐색을 합니다.
하지만 이분 탐색 원리상 end가 start 보다 절대 앞에 나올 수 없으며, 이때는 탐색을 다해봤지만 해당 값을 찾지 못했다는 의미이기 때문에 중단이 되는 겁니다.
두번째 중단점 : 원하는 값을 찾은 경우
start, end를 바꿔가면 중앙값으로 탐색을 하던 중 원하는 값이 나오면 해당 값을 반환하면서 중단하는 겁니다.
탐색 범위 좁히는 계산
탐색 범위를 조정하는 코드 start = mid+1, end = mid-1 이 정확히 입력되어야 합니다.
이분 탐색의 기본 조건 정렬
당연하지만 이분 탐색이 성립하기 위해서는 탐색 범위가 되는 리스트가 정렬이 되어야 합니다.
머리로 알아도 코드에서 생략한다면….
참 쉽지만 처음에는 어려웠던 이분 탐색이였습니다…ㅎㅎㅎ
참고하면 좋은 글
