[알고리즘] 매개변수 탐색(Parametric Search)과 이분 탐색(Binary Search)

출처: unsplash.com

 

내가 작년에 바이너리 서치에 대해 올린 적이 있다.

이번에 문제 풀이에서 바이너리 서치와 매개변수 탐색을 이용하는 문제를 풀고 다시 개념을 공부해보려 한다.

 

 

이분 탐색 복습(Binary Search)

이분 탐색을 간단하게 복습을 해보자.

아래 gif을 보면 이분 탐색이 어떻게 돌아가는지 바로 이해를 할 수 있을 것이다.

 

아래가 일반 검색 방법이고 위가 이분 탐색 방법인데,

일반 탐색과는 다르게 중간 지점과 시작점, 끝지점을 정해서 중간값을 찾아야 하는 값과 비교 후 대소에 따라 범위를 줄여가면서 탐색한다.

이분 탐색은 리스트가 정렬되어있어야 한다는 점이 특징이다.

중간값을 기준으로 대소를 비교하기 때문에 조건에 부합하지 않은 절반의 데이터를 걸러가면서 탐색하기 때문에 탐색 시간이 효과적으로 줄어든다.

 

 

매개 변수 탐색(Parametric Search)

매개변수 탐색은 조건을 만족하는 최댓값을 구할 때 쓸 수 있는 탐색 방법이다.

매개변수 탐색은 이분 탐색을 통해 최종 답안에 가까워져 가는 방식으로 문제를 해결한다.

이분 탐색의 mid의 값이 바로 정답이 되지는 않지만, 정답이 될 수 있는지 없는지 여부는 판단할 수 있다.

 

이제 문제를 통해 알아보자.

백준의 대표적인 매개 변수 탐색 문제인 랜선 자르기 문제이다.

 

랜선 자르기, Silver 2, 1654번

 

문제 설명은 생략하고, 문제를 어떻게 풀어야 하는지 알려 주겠다.

랜선을 잘라서 필요한 랜선의 개수 N개 이상이 될 수 있는 최댓값을 구해야 한다.

 

먼저 이분 탐색을 위한 범위를 저장해 주어야 한다. 어차피 이분 탐색이 워낙 빨라서 1부터 입력받은 최댓값까지로 설정해도 된다.

처음의 1을 start(left), 가장 큰 값인 802를 end(right), start와 end의 중간값을 mid로 설정한다.

 

여기서 mid값이 정답이 될 수 있는지 확인한다.

입력으로 주어진 802, 743, 457, 539를 mid값인 401의 길이로 잘라보면 2, 1, 1, 1개가 나오는데 우리에게 필요한 양인 11개(N)보다 4개가 부족하다.

 

여기서 2가지의 사실을 알 수 있다.

401은 정답이 아닌 것(결정, 매개변수 탐색).
401보다 큰 값도 정답이 아님(이분 탐색).

어차피 401보다 커 봤자 개수가 더 늘어나지는 않을 것이기 때문이다.

 

이 계산 1번으로 벌써 탐색 범위를 1 ~ 802에서 1 ~ 400으로 절반을 줄였다.

바로 다음 계산을 해보자.

2번째 계산에서는 첫 번째에서 제외된 값들이 있기 때문에 start(left), mid, end(right)를 새롭게 설정해 주어야 한다.

start는 그대로 두고, end를 첫 계산의 mid - 1(400)로 변경한다. mid(401)은 정답이 아니기 때문이다.

mid값도 새로 정해진 start와 end에 맞게 새로 구해준다.

 

다시 mid가 정답이 될 수 있는지 확인한다.

mid가 200일 때는 입력으로 주어진 802, 743, 457, 539에다가 200을 나눈 값의 합이 11인데 우리에게 필요한 값인 11(N)이랑 같다.

그러면 200은 정답이 될 수 있다는 뜻이 된다(정답 확정 아님).

위의 예제는 200이 정답이 맞다(201부터는 나눈 합이 10개). 하지만 다른 케이스에서는 200이 최댓값인지 알 수 없기 때문에 정답이라고 확정 짓지 않고 정답일 수 있는 값으로 놔두는 것이다.

 

이 계산으로 다시 범위를 반으로 좁힐 수 있다.

start를 200으로, end를 400으로 설정하고 mid를 300으로 설정한다.

위 과정을 반복하면 mid값과 end값이 계속 변동되어 결과로 이런 모습이 될 것이다.

초록색  부분이 정답이 될 수 있는 부분이고, 빨간색이 정답이 아닌 부분일 때, 남은 숫자는 201, 202가 나오는데 202와 201 모두 계산을 해본다. 위에서 언급했듯이 201인 경우에는 값이 10개가 나오기 때문에 최종적인 답은 200이 되는 것이다.

 

이론적인 부분은 설명이 되었으니 코드로 알아보자.

핵심 부분인 탐색 코드만 보여주겠다.

우선 main에 탐색 함수를 실행한다. start의 초기값은 1, end의 초기값은 입력값의 최댓값(max), mid는 max / 2로 설정한다.

binarySearch(1, max / 2, max)

 

 

binarySearch 함수에서는 

mid를 기준으로 입력값을 나눈 결과를 계산하고, 그 값의 결과에 따라 재귀 함수의 파라미터를 설정해 주었다.

var cut = 0
for (i in 0 until lan.size) {
    cut += lan[i] / mid
}

 

 

cut이 구해야 하는 양(cnt) 보다 크거나 같으면 mid를 기준으로 end까지의 값들이 모두 정답이 될 수 있다.

그 사실을 고려해서 start, mid, end를 설정해 주고 재귀를 돌린다.

// 자른 값(cut)이 구해야 하는 양(cnt)보다 크거나 같으면 mid를 기준으로 이전의 값들은 모두 정답이 아니게 된다.
if (cut >= cnt) {
    // mid 이후의 값으로 범위를 다시 설정해 재귀 함수 호출
    binarySearch(mid, mid + (end - mid) / 2, end)
}

 

cut이 구해야 하는 양(cnt) 보다 작으면 start부터 mid까지의 값들이 정답이 될 수 있다.

// 자른 값(cut)이 구해야 하는 양(cnt)보다 작은 경우 mid를 기준으로 이후의 값들은 모두 정답이 아니게 된다.
else {
    // mid 이전의 값으로 범위를 다시 설정해 재귀 함수 호출
    binarySearch(start, start + (mid - start) / 2, mid)
}

 

재귀를 반복하다 보면 start와 mid가 같아지는 시점이 오게 된다. 그러면 start(mid)와 end 총 2개의 값이 남게 되는데, 최댓값을 구해야 하기 때문에 start(mid) 보다 큰 값인 end를 이용해 cut을 구해본다.

만약 end를 이용한 resultCut이 구해야 하는 양보다 작으면 최종 답은 start(mid)가 된다. 그렇지 않다면 end가 될 것이다.

if (start >= mid) {
    var resultCut = 0
    for (i in 0 until lan.size) {
        resultCut += lan[i] / end
    }

    if (resultCut < cnt) println(start)
    else println(end)

    return
}

 

 

구현 중 주의할 점

매개 변수 탐색(이분 탐색)을 처음 구현할 때는 start, mid, end의 값을 어떻게 변경해야 할지 혼동이 올 수 있다.

천천히 생각해 볼 필요 없는 값들을 잘 버려서 모두 매개 변수 탐색 문제를 해결해 보자.

 

출처

https://adjh54.tistory.com/187

[Java/알고리즘] 이진 탐색(Binary Search) 이해하기

https://sete3683.tistory.com/50

매개 변수 탐색(parametric search, 파라메트릭 서치)