알고리즘
탐색은 데이터에서 원하는 값이나 위치를 찾는 알고리즘입니다. 선형 탐색, 이진 탐색, lower_bound·upper_bound, 답을 이분 탐색하기, 해시 조회를 다룹니다.
탐색은 데이터 모음에서 원하는 값을 찾거나, 어떤 조건이 처음으로 성립하는 위치를 찾는 일입니다. 선형 탐색은 원소를 하나씩 비교하므로 어떤 데이터에도 쓸 수 있고, 이진 탐색은 정렬된 구간을 매 단계 절반으로 줄여 원소 100만 개에서도 약 20번의 비교로 답을 찾습니다. 정확히 같은 키만 찾는다면 해시 테이블이 평균 상수 시간에 답합니다.
거의 모든 프로그램이 무언가를 찾기 때문에 탐색은 가장 기본이 되는 알고리즘입니다. 데이터베이스 색인, 자동 완성, 로그 분석, 라우팅 테이블이 모두 탐색에 기대고 있습니다. 이진 탐색은 배열에만 쓰이지도 않습니다. 예/아니오 조건이 범위 안에서 한 번만 바뀐다면 답 자체를 이진 탐색할 수 있어서, 코딩 테스트의 많은 최적화 문제가 짧고 확실한 코드로 바뀝니다.
먼저 선형 탐색과 닫힌 구간 이진 탐색을 직접 작성해 보고, 이어서 반열린 구간의 lower_bound·upper_bound 꼴을 경계 처리가 자연스러워질 때까지 익히는 것이 좋습니다. 작은 배열로 추적표를 그려 보고, 직접 만든 코드를 Python bisect 모듈과 무작위 입력으로 비교해 검증한 뒤, 최적화 문제로 답을 이분 탐색하기와 삼분 탐색을 연습합니다.
원소를 하나씩 비교하며 O(n) 시간이 걸립니다. 정렬이 필요 없고, 원소가 적을 때는 가장 빠른 선택인 경우가 많습니다.
정렬된 구간을 매 단계 절반으로 줄여 O(log n) 시간에 값을 찾습니다. 반복문으로 구현하면 추가 메모리는 O(1)입니다.
값 이상, 또는 값 초과인 첫 위치를 돌려줍니다. 두 결과의 차이가 중복 개수이며, Python bisect 모듈이 두 함수를 모두 제공합니다.
매개 변수 탐색은 '가능한 가장 작은 값은 무엇인가'를 예/아니오 판정으로 바꾸고, 가능한 답의 범위를 이진 탐색합니다.
lower_bound는 반열린 구간 [lo, hi)를 써서 값이 x 이상인 첫 인덱스를 돌려줍니다. 가운데 값이 x보다 작으면 왼쪽 절반을, 그렇지 않으면 오른쪽 절반을 버립니다. contains는 그 인덱스로 값이 있는지 확인하고, 마지막 줄은 결과가 표준 라이브러리 bisect.bisect_left와 같은지 확인합니다.
searching.py
from bisect import bisect_left
def lower_bound(a, x):
"""Return the first index i with a[i] >= x (len(a) if there is none)."""
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x:
lo = mid + 1
else:
hi = mid
return lo
def contains(a, x):
i = lower_bound(a, x)
return i < len(a) and a[i] == x
if __name__ == "__main__":
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(lower_bound(data, 23), contains(data, 23)) # 5 True
print(lower_bound(data, 24), contains(data, 24)) # 6 False
print(lower_bound(data, 24) == bisect_left(data, 24)) # True
python searching.py탐색 에 관해 묻고, 경험을 나누고, 의견을 주고받는 곳입니다.
아직 토론이 없습니다. 첫 이야기를 시작해 보세요.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.