백준 공유기 문제, 프로그래머스 징검다리 같은 parametric search 문제를 풀면서 그동안 중구난방으로 해왔던 custom binary search를 조금 더 정형적으로 해보도록 하자.
이진 탐색 기본 구조 : 범위 설정 - 기준값 도출 - 범위 재설정 반복
검색을 할 범위를 left, right로 두고 그 중간인 middle이 조건에 맞는지 검색한다. 조건에 맞는 방향으로 범위를 축소시켜 원하는 답이 한 개로 좁혀질 때까지 탐색을 반복하는 것이 이진 탐색의 기본 원리이다. 목표 값이 middle값보다 작으면 right값을 middle 이하로 조정하여 기준값보다 작은 범위에서 탐색하고, 반대라면 left값을 middle 이상으로 조정하여 기준값보다 큰 범위에서 탐색한다.
이 때 left와 right 범위를 정확히 어떻게 조정해야 할지, 그리고 반복문 조건을 어떻게 설정해야 할지 상세한 구현을 이번 기회에 딱 정리하도록 하겠다.! (이하 left를 l, right를 r, middle을 mid로 칭하겠음)
1. 반복문 설정 : 무조건 while l<r
헷갈리니 아예 while l<r으로 박아놓자. 답이 l==r일 때 1개만 나오도록 middle 설정을 하는 것이 마음 편하다.
2. 기준값 middle
left와 right의 중간값인 middle은 custom 이분탐색을 통해 찾고자 하는 답이 "조건을 만족하는 값의 최솟값"인지, "조건을 만족하는 값의 최댓값인지"에 따라 달라진다.
# 조건을 만족하는 최솟값 : mid = (l+r)//2
최솟값은 범위의 "오른쪽"에서 제일 좌측의 것을 구한다고 이미지화하자. 그러려면 중간 포인터는 중앙보다 왼쪽 값을 가리켜야 범위 축소가 일어난다.
# 조건을 만족하는 최댓값 : mid = (l+r+1)//2
최댓값은 범위의 "왼쪽"에서 제일 우측의 것을 구한다고 이미지화하자. 그러려면 중간 포인터는 중앙보다 오른쪽 값을 가리켜야 범위 축소가 일어난다.
3. 범위 재설정
# 조건을 만족하는 최솟값
최솟값을 찾을 땐 범위의 오른쪽에서 구하는 것을 이미지화하자고 했다.
l = mid+1, r = mid로 업데이트하자.
# 조건을 만족하는 최댓값
최대값은 범위의 "왼쪽"에서 구하는 것을 이미지화하자고 했다.
l = mid, r = mid - 1로 업데이트하자.
l,r값을 mid+-1이 아니라 mid 자체로 업데이트하면 반복문을 못빠져나가지 않나? 싶을 수 있을텐데, 최솟값을 구할 때 mid값 (l+r)//2은 항상 r보다 작고(l<r이기 때문), 최댓값을 구할 때 mid값 (l+r+1)//2는 l보다 크므로 범위 축소가 무조건 일어난다. 결국 반복문을 돌면서 l과 r은 정확히 하나의 값으로 수렴하게 되고, 이것이 답이된다.
관련한 문제다.
프로그래머스 : 징검다리
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
"조건을 만족하는 값 중 최댓값을 구하는 문제"이다. 최댓값은 좌측에서 가장 오른쪽의 값을 선택하는 것을 이미지화 해야한다고 했다.
mid = (l+r+1)//2로 두고, l=mid, r=mid-1로 범위를 축소하여 답을 구하자.
def solution(distance, rocks, n):
can = len(rocks) - n
rocks.sort()
l,r = 0,distance
while (l<r):
m,count,cur = (l+r+1)//2,0,0
for i in range(len(rocks)):
if (rocks[i]-cur>=m):
count += 1
cur = rocks[i]
if (distance - cur<m):
count -= 1
if (count >= can):
l = m
else:
r = m-1
return l
프로그래머스 : 입국 심사
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이번엔 "조건을 만족하는 값 중 최솟값"을 구하는 문제다. 우측에서 가장 왼쪽의 값을 선택하는 것을 이미지화 한다고 했다. mid = (r+l)//2, 값의 업데이트는 l = mid+1, r=mid로 축소하자.
def solution(n, times):
l,r = 0,10**18
while l<r:
m = (l+r)//2
if (n > sum(m//i for i in times)):
l = m+1
else:
r = m
return l
# 백준 : 공유기 설치
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
징검다리와 매우 흡사한 문제. 공유기간 최소 거리를 최대로 하면서 c개의 공유기를 모두 설치할 수 있도록 구성해야한다.
"조건을 만족하는 최댓값"이므로 좌측에서 가장 오른쪽 값을 찾는다는 것을 의식해야 하며, 값을 좌측으로 좁힐 때 r = mid-1을 사용하도록 구성한다.
import sys;input=sys.stdin.readline
n,c = map(int,input().split())
x = []
for _ in range(n):
x.append(int(input()))
x.sort()
# 인접한 공유기 거리의 최솟값이 최대가 되도록
l,r = 0,10**9
while (l<r):
# mid : 허용 최솟값. 거리가 얘 이상이어야 설치 가능
mid,count,cur = (l+r+1)//2,1,x[0]
for i in range(1,n):
if (x[i]-cur >= mid):
# i 설치가능
count += 1
cur = x[i]
if (count < c):
# 최솟값 높여서 공유기 더 설치할 수 있도록
r = mid - 1
else:
l = mid
print(l)