[이분탐색] 이분탐색 이해하고 구현하기 Parametric Search 구현 시 맞왜틀 방지(백준 2805 python)

 

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

문제

 

나무들의 길이 배열과 절단할 높이 H 가 있을 때,

나무 길이 배열을 순회하며 H보다 높은 나무들은 잘리게 되고, 이때 잘린 부분의 총합을 X라고 한다.

X의 값이 M보다 크거나 같기 위한 절단할 높이 H의 최댓값을 구하라.

 

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

 

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

 

이 문제가 왜 이분탐색인지?

1. 주어지는 입력값이 아주아주 크니까 일반적인 구현으로는 못풀것 같다.
2. ~~가 가능한 / 만족하는 최솟값 / 최댓값을 구하는 문제이다.
3. 문제에서 정답으로 요구하는 값(여기서는 절단기 높이 설정값) 이 정답인지 검사하는 함수의 매개변수로 쓰인다.

이분 탐색 중, parametric search(검사하는 데에 사용하는 매개변수의 값을 이진탐색) 문제이다.

아래는 예제1을 알기 쉽게 엑셀에 표현한 사진

 

문제의 조건을 만족하는 최대 설정 높이는 15라는 것을 알 수 있다.

 

어영부영 짠 코드

 

입력

import sys
input = sys.stdin.readline

N, M = map(int, (input().split(' ')))
woods = list(map(int, input().split(' ')))

 

문제의 정답 후보를 매개변수로 하고, 문제에서 원하는 조건을 만족하는지 검사하는 함수

def calculateM(height):
    return sum(i-height if i-height>0 else 0 for i in woods)

 

parametric search를 구현한 부분

l = 0
h = 1000000000

while(l <= h):
    mid = (l+h)//2
    cutLength = calculateM(mid)
    if cutLength >= M:
        l = mid+1
    elif cutLength < M:
        h = mid-1

print(h)

while문을 탈출했을 때 h를 출력하며 정답~!

잘만 짠 것 같지만 아주 슬픈 비밀이 있다...

 

 

눈물나는 이분탐색 구현 방법

 

나만 이렇게했을수도 있지만, 이분탐색문제 (특히 parametric search) 풀 때마다 너무 고생스럽다....

맞왜틀 이라고 할 만큼의 확신도 없을뿐더러 틀리면 그냥 틀린 대로 딴 거 해보지 뭐~ 하고 계속해서 제출하는데, 백준 닳겠다.

while문 후보

while(l <= h):

while(l < h):

while(l + 1 < h):
  

 

조건 만족에 등호를 넣을까 말까~

if cutLength >= M:
elif cutLength < M:
       

if cutLength > M:
elif cutLength < M:
else: # 정확히 문제에서 요구하는 조건과 일치할때
		return mid # 방금 매개변수가 정답!

 

mid에 +1? -1? 그냥 mid?

if cutLength >= M:
    l = mid+1
    l = mid
elif cutLength < M:
    h = mid-1
    h = mid

이분탐색을 구현할 때 위의 후보들 중에 고민하지않고 바로바로 구현할 순 없을까?

 

 

아래 글을 2번정도 정독하니까 속이 다 시원했다.

https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

 

이분 탐색 문제는 정답이 포함되어 있는 [l,h] 구간을 절반으로 좁혀가며 진행된다.

[l, h]의 구간을 처음엔 [0,100000000]으로 잡았지만, 결국엔 정답 인덱스 answer를 포함하는

[answer-1, answer+1] 와 같은 구간으로 좁혀질 것이다.

 

 

 

위의 예제를 엑셀로 분석한 사진을 요약한 위 사진으로 알아보자,

 

정답에 해당하는 인덱스는 15이고, 현재 탐색 구간이 [14,16]까지 좁혀진 상황을 생각해 보자

[True, True, False]의 상황에서 l(=14)을 증가시켜도 되니까, 다음 검사 구간은 [15,16]이 될 것이다.

그러면, 구간 15,16의 길이는 2이며, 이 안에 문제의 조건을 만족하거나 만족하지 않게 되는 경계선이 존재한다는 뜻이다.

 

[True, False]의 상황에서 우리는 문제조건을 충족하면서 절단기 설정 기준값이 가장 큰, True에 해당하는 parameter를 정답으로 선택해야 한다.

그러므로 while문 종료 시 l이 정답! (참고로 h는 가장 처음으로 False가 되는 인덱스이다.)

 

개선된 코드

while(l+1<h):
    mid = (l+h)//2
    cutLength = calculateM(mid)
    if cutLength >= M:
        l = mid
    else:
        h = mid

print(h)

 

위의 이분탐색 코드 후보들 중에서

while(l+1<h):

if f(x) >= condition:
	l = mid
else:
	h = mid

를 고정적으로 선택하고, 문제가 결정하는 $f(x)$ 의 증가 감소 형태를 잘 생각하여, l=mid와 h=mid의 위치를 변경하는 것 말고는 고려할 것이 없다.

 

 

눈으로 결과만 보기에는 별 다를 거 없이 보일 수 있어도, 확신을 갖고 이분탐색 코드를 짠다는 점에서

맞왜틀 시간과 +1이냐 -1이냐 > 이냐 ≥ 이냐에 대한 고민의 시간을 줄일 수 있었음.