반씩 줄이자! 이분 탐색
안녕, 나 코딩냥이다냥! 4장에서 정렬을 배우면서 "정렬해두면 다음 걸음이 쉬워진다"고 했지? 오늘이 그 보상을 받는 날이라냥. 정렬된 데이터에서는 100만 개 중에 찾는 것도 스무 번이면 끝난다냥.
오늘의 학습 목표
- 이분 탐색이 왜 빠른지 횟수로 설명할 수 있다.
lo,hi를 움직이는 기본 골격을 손으로 쓸 수 있다.- 경계를 찾는다 — 값이 아니라 "여기서부터"를 찾는다.
- 답 자체를 이분 탐색하는 문제를 알아본다.
1단계 · 업다운 게임이라냥 (5분)
1부터 100 사이 숫자를 맞히는 게임을 해봤냥? 내가 "50!" 하면 너는 "업" 또는 "다운"이라고 답하지? 그게 이분 탐색이라냥.
한 번 물어볼 때마다 후보가 반으로 준다냥
100개를 7번에 끝낸다냥. 하나씩 물어보면 최악에 100번이라냥.
반씩 줄이면 2를 몇 번 곱해야 그 수가 되냐가 곧 질문 횟수라냥.
2를 20번 곱하면 약 100만이라냥. 그래서 100만 개에서 찾는 데 20번이면 충분하다냥. 10억 개여도 30번이라냥.
이걸 O(log n) 이라고 부른다냥.
단, 정렬되어 있어야만 쓸 수 있다냥.
"업/다운"을 판단하려면 가운데 값보다 큰 게 전부 오른쪽에 있어야 하기 때문이라냥. 정렬이 안 된 데이터에는 못 쓴다냥.
2단계 · 기본 골격 (10분)
def find(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return True
elif arr[mid] < target:
lo = mid + 1 # 오른쪽 절반만 남긴다냥
else:
hi = mid - 1 # 왼쪽 절반만 남긴다냥
return False다섯 개를 두 번 만에 찾았다냥. 손으로 이렇게 표를 그려보는 게 이분 탐색을 익히는 가장 빠른 길이라냥.
lo = mid + 1 의 +1 을 빼먹으면 무한 반복이라냥.
lo = mid 라고 쓰면 lo 가 그대로일 수 있어서 영원히 안 끝난다냥.
이미 확인한 mid 는 반드시 범위에서 빼야 한다냥.
코드가 멈추지 않으면 이걸 제일 먼저 의심하자냥.
3단계 · 값 말고 경계를 찾자냥 (12분)
실전에서는 "있냐 없냐"보다 "어디서부터냐" 를 더 자주 묻는다냥. 이걸 경계(lower bound)라고 한다냥.
target 이상인 값이 처음 나오는 위치를 찾는 코드라냥.
def lower_bound(arr, target):
lo, hi = 0, len(arr) # hi 가 len(arr) 라냥. -1 이 아니라냥
while lo < hi: # <= 가 아니라 < 라냥
mid = (lo + hi) // 2
if arr[mid] < target:
lo = mid + 1
else:
hi = mid # mid 도 답일 수 있으니 빼지 않는다냥
return lo기본 골격과 세 군데가 다르다냥. 헷갈리기 쉬우니 표로 보자냥.
경계 찾기에서 hi = mid - 1 이라고 쓰면 답을 건너뛴다냥. mid 자체가
정답일 수 있기 때문이라냥.
경계 하나로 개수를 센다냥
arr = [1, 3, 3, 3, 7, 9]
# 3 이상인 첫 위치 = 1
# 3 초과인 첫 위치 = 4
# 3의 개수 = 4 - 1 = 3a 이상 b 이하인 값의 개수는 이렇게 구한다냥.
(b 초과인 첫 위치) - (a 이상인 첫 위치)
파이썬에는 이미 만들어져 있다냥.
import bisect
bisect.bisect_left(arr, a) # a 이상인 첫 위치
bisect.bisect_right(arr, b) # b 초과인 첫 위치직접 구현할 줄 아는 것과 도구를 쓰는 것은 다른 일이라냥. 오늘은 둘 다 해보자냥.
4단계 · 답 자체를 탐색한다냥 (12분)
오늘의 하이라이트라냥. 지금까지는 배열 안을 찾았는데, 이번엔 답의 범위를 찾는다냥. 처음 보면 놀랍지만 원리는 똑같다냥.
문제는 이렇다냥 — 길이가 제각각인 랜선들을 잘라서 길이가 같은 랜선 k개를 만들 때, 한 개의 최대 길이는 얼마냥?
"최대 길이가 얼마냐"는 어렵다냥. 그런데 질문을 바꾸면 쉬워진다냥.
"길이를 200으로 하면 k개를 만들 수 있냥?"
이건 그냥 세보면 된다냥. 그리고 여기에 중요한 성질이 있다냥.
"된다"가 쭉 이어지다가 어느 순간부터 "안 된다"로 바뀐다냥. 이 경계를 찾는 거니까 이분 탐색이라냥!
lo, hi = 0, max(arr)
while lo < hi:
mid = (lo + hi + 1) // 2 # +1 이 중요하다냥
made = sum(x // mid for x in arr) # mid 길이로 몇 개 나오냥
if made >= k:
lo = mid # 되니까 더 길게 시도한다냥
else:
hi = mid - 1 # 안 되니까 줄인다냥
print(lo)mid = (lo + hi + 1) // 2 의 +1 을 빼먹으면 무한 반복이라냥.
lo = mid 를 쓰는 형태에서는, lo 와 hi 가 딱 1 차이일 때 mid 가
lo 와 같아져서 아무것도 안 줄어든다냥. +1 이 그걸 막아준다냥.
기억하는 법 — lo = mid 를 쓰면 mid 를 위로 올린다냥.
이 방식을 "매개 변수 탐색"이라고 부른다냥. 알아보는 신호는 이거라냥.
- 최댓값 중 최소 또는 최솟값 중 최대를 구하라
- 답을 하나 정해놓으면 되냐 안 되냐를 쉽게 판단할 수 있다
이 둘이 보이면 답을 이분 탐색하는 문제라냥.
오늘 배운 내용 정리
먼저 스스로 답해보고, "정답 보기"를 눌러서 맞는지 확인해보자냥!
이제 직접 풀어볼 차례다냥
오늘 문제는 다섯 개고 경계를 다루는 감각이 전부라냥. 1번은 기본이고,
23번은 경계, 45번은 답을 탐색한다냥. 막히면 손으로 표를 그려보자냥.
lo 와 hi 가 어떻게 움직이는지 서너 줄만 적어보면 길이 보인다냥. 가보자냥~