[Python] 이분 탐색

Logic

• low, high를 정한다.
• low가 high보다 작거나 같을 때까지 while문을 반복한다.
• while문 내에서 mid를 정한다.
• 탐색할 값이 mid보다 작다면 반틈으로 나눈 것 중에서 앞부분에 있다는 뜻이므로 high = mid - 1로 바꾼다.
• 탐색할 값이 mid보다 크다면 반틈으로 나눈 것 중에서 뒷부분에 있다는 뜻이므로 low = mid + 1로 바꾼다.

관련 문제

www.acmicpc.net/problem/2805

풀이보기

 

나무의 길이 최댓값이 매우 크기 때문에 그냥 구현하면 시간 초과가 발생한다.

이분탐색을 이용해서 절단기 높이 최댓값을 효율적으로 찾을 수 있다.

low = 0, high = 1000000000(최대)로 정해두고, 이분탐색을 통해서 각 경우의 절단된 나무길이를 구한다.

절단된 나무길이가 M미터보다 작으면 high = mid - 1로 한다.

절단된 나무길이가 M미터보다 크거나 같으면 low = mid + 1로 한다.

 

코드보기

N, M = map(int, input().split())
tree = [int(x) for x in input().split()]

low = 0
high = 1000000000
answer = 0

while low <= high:
    mid = (low+high)//2
    count = 0
    for i in range(N):
        if(tree[i] > mid):
            count += tree[i]- mid
    
    if(count < M):
        high = mid -1
    else:
        answer = mid
        low = mid + 1

print(answer)
    

 

www.acmicpc.net/problem/1789

풀이보기

주의할 점: 이분탐색으로 풀 때 sum을 구하는 과정에서 for문을 사용하면 시간 초과가 발생한다. 이 대신, 합의 공식[n*(n+1)/2]를 사용하여 sum을 계산해야한다. -> O(1)

 

코드보기

S = int(input())

low = 0
high = S
answer = 0

while low <= high:
    mid = (low+high)//2
    Sum = mid * (mid+1) //2 
    
    if(Sum > S):
        high = mid -1
    else:
        answer = mid
        low = mid + 1

print(answer)

 

www.acmicpc.net/problem/1300

풀이보기

1. low와 high 값을 지정한다. low = 0, high = k(최대 개수는 k를 넘을 수 없으므로)

2. low가 high를 넘기 전까지 while문을 실행한다.

   2-1. count는 현재 탐색 중인 값을 i(행 번호)로 나눈 몫의 합이다. 만약 그 값이 N보다 크다면 그 값은 N으로 한다. 한 행에 개수가 N보다 클 수 없기 때문

   2-2. count가 k보다 작다면 그 값은 mid보다 큰 쪽에 위치한 것이므로, low를 mid+1로 바꾼다.

   2-3. count가 k보다 크거나 같다면, 그 값은 mid보다 작은 쪽에 위치한 것이므로, high를 mid-1로 바꾼다. 그리고, answer을 mid로 한다. low가 high보다 커지는 순간 그 때의 answer가 최종 답이다.

코드보기

N = int(input())
k = int(input())

answer = 0
low = 0
high = k

while low <= high:
    count = 0
    mid = (low+high)//2

    for i in range(1, N+1):
        count += min(mid//i, N)
    
    if(count < k):
        low = mid + 1
    else:
        answer = mid
        high = mid -1

print(answer)