이분탐색(파라메트릭 서치)문제 푸는 요령

이분탐색을 이용한 파라메트릭 서치 문제는 구현방법이 비슷한데, 이번 글에서는 그 중 어떤 것의 개수가 주어졌을 때 그 개수를 먼저 찾고 추가로 최솟값이나 최대값을 구해야 하는 유형의 문제풀이 요령을 다룬다.

 

이런 유형은 거의 다 풀었음에도 정답과 근접한 오답이 나와 해설을 보면 내 코드와 한두 줄정도가 달랐다.

 

그 다른점은 아래와 같다.

• 이분탐색 반복문 내 분기문의 부등호 설정
• res를 선언 후 (lt를 늘리거나 rt를 줄일 때) 즉 mid를 증감시키는 경우 중 한가지 경우에서만 res에 mid값을 갱신

이 사소한 차이 때문에 여러 문제를 풀면서 비슷한 이유로 오답이 나왔던 것이다.

 

'마구간 정하기'코드를 예시로 들어 해설자는 왜이렇게 풀었는지 그리고 이렇게 코드를 짜야하는 이유에 대해 알아보자.

 

예시 코드

lt = 1
rt = h[-1]
res = 0

def count(m):
    cnt = 1
    prev = h[0]
    for i in range(1, n):
        if h[i] - prev >= m:
            cnt += 1
            prev = h[i]
    return cnt


while lt <= rt:
    mid = (lt + rt) // 2
    if count(mid) >= c:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1
print(res)

1. 분기문의 부등호를 설정하는 기준

이분탐색의 문제는 필요에 맞게 정의한 함수의 리턴값을 기준으로 mid의 증감을 결정한다.

함수의 리턴값을 다루는 상황은 총 세가지로 나눌 수 있다. 쉬운 이해를 위해 변수명은 예시와 동일하게 한다.

1. count(mid) > c일 때
2. count(mid) < c일 때
3. count(mid) == c일 때

물론 문제에 따라 세가지 상황을 if, elif, else로 나눠 풀 수있겠지만 위 예시처럼 개수를 동일하게 맞춘 뒤에도 추가적인 최적화가 필요할 때는 if, else문만 작성해서 두가지 케이스로 분기하는게 가장 효율적이고 가독성도 좋았다.

 

그렇게 두가지로 분기하게 되면 아래 두 경우 중 하나를 선택하게 된다.

#1
if count(mid) >= c:
	~
else:
	~
 
#2
if count(mid) <= c:
	~
else:
	~

이번 예시와 같은 문제는 count(mid)==c가 참인 mid값을 발견했다고 해서 그 mid값이 문제의 정답이라고 단정지을 수 가 없다.

위 조건이 참이 나오도록하는 mid값이 여러개가 있기 때문이다.

보통 이런 유형의 문제는 문제에서 요구하는게 최솟값인지 최댓값인지에 따라 개수를 충족하는 mid를 구한 이후에도 mid값을 세밀하게 조정해야하며 그렇기 때문에 상황에 맞게 if count(mid)>=c: else:  또는 if count(mid)<=c: else:로 조건을 설정해서 반복문이 끝날 때까지(lt > rt일 때 까지) mid를 증감 시켜야하는 것이다.

 

 

2. 왜 분기문 중 하나에서만 res을 갱신시켜 주는지?

코드를 보면 count(mid) >= c가 참일 때에만 현재 mid값을 res에 갱신한다.

이유가 뭘까?

이런 유형의 문제는 주어진 개수와 함수의 리턴값이 일치하는 mid값이 여러개가 있다고 위해서 언급한 바있다.

그래서 개수가 맞는 mid값을 구했음에도 반복문이 끝날 때까지 mid값을 증감시키는 데 이 과정에서 함수의 리턴값과 주어진 개수가 일치하지 않는 mid값으로 회귀하는 경우가 있을 수 있다. 만약 두가지 분기에서 모두 res값을 갱신시켜준다면 반복문이 종료됐을 때 쌩뚱맞은 결과값이 res에 저장될 수 있기 때문에 이를 미연에 방지하기 위한 장치라고 생각하면 되겠다.

 

 

이런 유형을 혼자 풀었을 때는 세가지 분기로 나눠 풀기도 했고 mid값 증감 시 모두 res값을 갱신하기도 했다.

그 결과, mid값을 세밀하게 조정하기 위해 else문의 코드가 너무 복잡해졌고 엉뚱한 답이 나오기도 했다.

 

위 이유를 근거로 비슷한 유형의 문제가 나왔을 때 해설 처럼 풀 것을 권장한다.