★Binary Search Upper-Intermediate I - 6 Solved★

😻 이분탐색 알고리즘을 적용해야 함을 인지하는 부분이 제일 중요하다. 이분탐색을 풀어야 하는 문제의 판별법은

 

① 노가다성이 들어간다. 일단, 내가 원하고자 하는, 무언가를 일일이 문제의 조건을 충족해가며 비교해가는 과정이 들어간다면 이분탐색 또는 매개변수 탐색 유형임을 고려해보자

 

② ~자르기와 같은 주어진 최소, 최대 일렬로 나열된 줄에서 범위를 줄여가며 최종 target(point일 수도 있고, 주어진 범위의 길이일 수도 있다)을 찾는 문제라면 이분탐색을 고려해보자

---

★ 1654 랜선 자르기 ★

 

import sys
input=sys.stdin.readline

K,N=map(int,input().split())
ls=[int(input())for _ in range(K)]

start,end=1,max(ls) #0,max(ls)-1 x
ans=0
while start<=end:
    cnt=0
    mid=(start+end)//2

    for l in ls:
        cnt+=(l//mid)

    if cnt>=N:
        ans=mid
        start=mid+1

    else:
        end=mid-1
print(ans)

 

😻 이분탐색 유형임을 아는 것이 중요

 

😻 여러 랜선 중 최대 길이를 max로 잡은 뒤, 정확히 1부터 max 사이의 중간 길이부터 시작

 

① 각 랜선별로 중간길이의 랜선으로 나누었을 때의 개수 count

 

② 만약, N 이상이라면, 찾고자 하는 간격 랜선 길이를 더 늘려서 찾을 가능성이 있으므로 start=mid+1로 놓고 탐색

(문제에 'N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다')

 

③ N미만이라면, 간격 랜선 길이를 더 줄일 필요가 있으므로 end=mid-1로 놓고 탐색

 

④ start<=end가 될 때까지 계속 반복 (end 초기값을 애초에 제일 긴 랜선의 길이로 설정했기 때문에 랜선의 길이가 이보다 더 작거나 클 확률 x)

---

★ 2512 예산 ★

 

import sys
input=sys.stdin.readline

N=int(input())
budgets=list(map(int,input().split()))
max_budget=int(input())

end=max(budgets)
start=1
ans=1
mid=(start+end)//2
while start<=end:
    s=0
    mid=(start+end)//2

    for budget in budgets:
        if mid<budget:s+=mid
        else:s+=budget

    if max_budget>=s: #need to increase the budget line
        start=mid+1
        ans=max(ans,mid)
    else: #decrease the budget line
        end=mid-1
print(ans)

 

😻 상한액을 target으로 찾아야 하고, 노가다성(?)으로 일일이 최대예산에 제일 가까운 상한액인지 찾아야 하는 문제이기에, (1) target 탐색 + (2) 조건 부합 여부 - 두 가지 조건을 충족하므로 이분탐색 유형

 

😻 이분탐색 주의점) 수가 제일 작을 때, 항상 예외 설정 확인하기

→ 만약 최솟값 3개의 지방이 존재하고, 각각의 예산이 1, 1, 1이며 총 예산은 3이라면, 상한액은 1로 default 설정 (최소 1은 가져가야 함) (ans=1)

 

😻 이분탐색 진행 → mid를 상한액으로 정하고, if문으로 부합하는 지 확인, 이 때 max_budget 총 예산보다 작게 나왔다면, 답의 후보가 되므로 수시로 max(ans,mid) update해, 답의 후보가 될 수 있는 결과 중 최댓값을 ans 변수로 출력하게 설정!

---

★ 2805 나무 자르기 ★

 

import sys
input=sys.stdin.readline
from collections import Counter

N,M=map(int,input().split())
trees=Counter(map(int,input().split()))

start=0
end=max(trees)
res=0

while start<=end:
    total=0
    mid=(start+end)//2

    cut=[(h-mid)*trees[h] for h in trees if h>mid]
    
    if sum(cut)>=M:
        res=max(res,mid)
        start=mid+1
    else:
        end=mid-1
print(res)

 

😻 노가다성으로 여러 번 자르면서 조건을 만족하는 경우 중 나무를 자르는 높이 최댓값을 구하는 문제 → 이분탐색 사용!

 

😻 collections의 Counter 함수를 사용하면, Counter 함수로 중복하는 여러 높이가 있을 경우 일일이 if문을 돌지 않고, 반환형 dictionary의 value를 그대로 곱하기만 하면 되므로 성능 향상

 

ex)

from collections import Counter
print(Counter(["hi", "hey", "hi", "hi", "hello", "hey"])) #Counter({'hi': 3, 'hey': 2, 'hello': 1})

---

★ 2343 기타 레슨 ★

 

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
l=list(map(int,input().split()))
start,end=max(l),sum(l)
while start<=end:
    mid=(start+end)//2
    grp_sum=0
    cnt=1
    for x in l:
        grp_sum+=x
        if grp_sum>mid:
            grp_sum=x
            cnt+=1
            if cnt>M:
                break
    if cnt>M:
        start=mid+1
    else:
        ans=mid
        end=mid-1
print(ans)

 

😻 아래 그림으로 한 번에 설명된다.

: 블루레이 크기가 커질수록 블루레이 개수는 작아지는 반비례 관계. ans update 가능한 구간은 블루레이 개수가 M보다 작은 케이스로 문제에 '블루레이의 개수를 가급적 줄이려고 한다'라고 되어있기 때문. 가능과 불가능 영역을 정확히 구분해서 ans update 코드를 적절 if문 넣기

추가로 start와 end는 x가 묶음합이므로 최솟값 단일 1개 묶음합부터 전체 합까지의 범위 설정

---

★ 13702 이상한 술집 ★

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
kettles = []
for _ in range(N):
    kettles.append(int(input()))
i = 1
j = max(kettles)
ans = 0
while i <= j:
    mid = (i+j)//2

    ppl=0
    for kettle in kettles:
        ppl+=(kettle//mid)

    if ppl < K:
        j = mid - 1
    else:
        ans = mid
        i = mid + 1
print(ans)

 

😻 구하고자 하는 막걸리 용량을 1부터 max(kettles)로 두고, mid 값에 따라, 정해진 용량에 맞게 따를 수 있는 사람의 수를 ppl이라 하자. 그러면 해당 ppl값이 K보다 큰 지 / 작거나 같은 지에 따라 start 또는 end 값을 바꾸어 범위를 업데이트.(이 때 막걸리 용량 첫 범위를 0이 아닌 1로 두어, 0으로 나누는 에러가 발생하지 않게 조절. 문제 제약 범위 상 0이 될 수는 x)

---

★ 31264 사격 ★

import sys
input = sys.stdin.readline
from bisect import bisect_right

N,M,A=list(map(int,input().split()))
ss=list(map(int,input().split()))
ss.sort()

start,end=1,ss[-1]
ans = 0
while start<=end:
    mid = (start+end)//2
    cur = mid
    cur_ans = 0
    for _ in range(M):
        cur_pos = bisect_right(ss, cur_ans+cur) - 1
        if cur_pos == -1:
            break
        cur_ans += ss[cur_pos]
        
    if cur_ans < A: #fail
        start = mid + 1
    else: #succeed
        ans = mid
        end = mid - 1
print(ans)

 

😻 매개변수 탐색 안에 이분탐색이 있는 특수한 형태의 문제.

 

😻 내가 쏘는 사격 점수를 mid로 하고,

① 쏘는 점수 포함 아래의 값중 쏠 수 있는 최댓값을 골라 사격함(bisect_right - 1로 cur_pos 정함. 이 때 쏠 수 없는 경우는 bisect_right - 1결과가 -1이 나오므로 이 때 break.

② 최종적으로 add up한 결과인 cur_ans가 A보다 작다면 fail / A보다 크거나 같다면 succeed. fail이라면 start = mid + 1 / succeed라면 end = mid - 1 그리고 ans = mid 업데이트로, 조건을 만족하는 '최솟값' mid를 출력해주면 된다.

---