탐색
답을 이분 탐색하기
되는지 안 되는지만 물어보기
바나나 더미 네 개(3 · 6 · 7 · 11개)를 8시간 안에 다 먹어야 합니다. 한 시간에 한 더미만 먹고, 남아도 그 시간은 끝납니다. 한 시간에 몇 개씩 먹으면 될지 속도를 골라 보세요.
한 시간에 한 더미만 먹고, 남아도 그 시간은 끝납니다. 먼저 맞혀 보세요. 한 시간에 5개씩 먹으면 8시간 안에 다 먹을 수 있을까요?
가장 느린 속도는 4였습니다. 속도가 4일 때 8시간이라 8시간 안에 되고, 하나 더 느리면 10시간이라 안 됩니다.
시험한 횟수는 0번이었습니다. 속도 후보가 11개라 1부터 하나씩 해 보면 최대 11번, 반씩 줄이면 최대 4번입니다.
값을 찾는 게 아니라 되는지 안 되는지만 묻기안 됨 → 됨이 한 번 바뀌는 자리 = 답
이분 탐색을 정렬된 줄이 아니라 답이 될 수 있는 값(속도)에 쓴 것 = 답을 이분 탐색하기(파라메트릭 서치)입니다. 속도 하나를 시험할 때마다 후보가 절반씩 줄었습니다.
안 됨 다음에 됨이 한 번만 바뀐다
- 느린 속도에서 안 되면 — 더 느린 속도도 전부 안 된다
- 되는 속도에서는 — 더 빠른 속도도 전부 된다. 해 보지 않아도 칸이 칠해진 이유다
- 되다 안 되다 하면 — 반씩 버릴 수 없다. 한 번만 바뀌어야 쓴다
되는지 묻는 함수 하나와 이분 탐색
can_finish— 속도 하나를 받아 걸리는 시간을 더해 8시간 이하인지만 답한다. 문제마다 바뀌는 곳은 여기뿐이다(p + speed - 1) // speed— 남아도 그 시간은 끝나는 올림이다hi = mid— 되면 mid 도 답일 수 있어 버리지 않고 남긴다
다음을 눌러 보세요. 중간에 한 번 물어봅니다. 흐리게 지워진 칸은 안 되는 속도로 확정, 초록 칸은 되는 속도로 확정입니다. can_finish 안(2~5번 줄)은 한 스텝으로 묶었습니다.
다음을 눌러 한 줄씩 넘겨 보세요
lo = 1 hi = 11
- 1def can_finish(piles, speed, h):
- 2 hours = 0
- 3 for p in piles:
- 4 hours += (p + speed - 1) // speed
- 5 return hours <= h
- 6
- 7def min_speed(piles, h):
- 8 lo, hi = 1, max(piles)
- 9 while lo < hi:
- 10 mid = (lo + hi) // 2
- 11 if can_finish(piles, mid, h):
- 12 hi = mid
- 13 else:
- 14 lo = mid + 1
- 15 return lo
같은 코드로 제한 시간만 8시간에서 11시간으로 늘리면 가장 느린 속도는 얼마일까요?
답을 이분 탐색할 때 틀리는 자리
- 올림을 빼면 —
p // speed는 남은 바나나를 무시한다. 속도가 3일 때 8시간으로 나와 답이 3이 되는데, 실제로는 10시간이 걸린다 lo <= hi와hi = mid를 섞으면 — lo 와 hi 가 4로 만나도 mid 가 4라서 hi 가 다시 4가 된다. 끝나지 않는다- 상한을 작게 잡으면 —
hi를 3으로 시작하면 3이 나오는데 3으로는 10시간이 걸려 안 된다. 상한은 반드시 되는 속도여야 한다 hi = mid - 1로 쓰면 — 되는 mid 를 버려서 답을 놓친다. 제한이 6시간이면 답은 6인데 5가 나온다
문제에서 이 말이 보이면
되는지 판정하는 함수만 만들 수 있으면 됩니다. 판정이 한 번만 바뀌는 문제라면 이분 탐색이 나머지를 해 줍니다.
다음 장에서는 한 걸음씩 번져 가며 최단 거리를 재는 격자 BFS 를 봅니다.