이분 탐색 ( Parametric Search, lower, upper Bound / Swift ) - 2

파라메트릭서치(Parametric Search) 

조건에서 최소, 최대를 찾는 문제에서 결정 문제로 변경하여 탐색하는 알고리즘을 말합니다.

 

이전까지는 정렬되어 있는 배열에서 해당 값이 있는지 파악했지만,

 

 

파라메트릭서치에서는 조건이 가질 수 있는 최소, 최대 값을 결정하고 (start, end)

 

해당 하는 값이 조건에 만족하는지 파악하여, 구간별로 탐색하는 것을 의미합니다.

 

 

예시 문제

김OO 은 게임 승률이 50% 가 넘으려면 몇 판을 해야하는지 궁금합니다.

 

무조건 게임은 승리한다고 가정했을 때, 최소한으로 몇판을 이겨야 하는지 승수를 구하시오.

 

( 단 비기는 경우는 없다고 가정하고, 답은 Int 범위를 넘지 않는다. )

 

총 게임 횟수: 50, 승리 : 1, 패배 : 49

 

 

 

위 경우에 일반적으로 게임 횟수 1 부터 승률 50%가 될 때까지 증가시키면 쉽게 풀 수 있습니다.

 

 

 

하지만 문제에서 게임 횟수가 Int 범위만큼 커지거나, 99% 가 되는 승률을 구하라고 한다면

 

시간복잡도가 기하급수적으로 올라가게 됩니다. ( 대부분 코딩테스트에서 요구하는 2초를 넘기게 됩니다. )

 

 

이런 경우에 파라메트릭 서치로 해결할 수 있습니다.

 

게임 최소 횟수 ~ 최대 횟수 만큼 이분 탐색을 하여 탐색할 구간을 지정합니다.

 

중간 값을 넣었을 때, 승률이 작다면 ( start = mid + 1 ) 승률이 크다면 ( end = mid + 1 )

 

파라메트릭 서치를 활용하여 잘 접근한 것 처럼 보이지만, 실제로는 올바른 값이 나오지 않습니다.

 

그 이유로는 48 ~ Int MAX 범위까지 모두 percent 가 50% 가 넘기 때문입니다.

 

따라서 if percent >= 50 에서 1 ~ 47 값을 제외한 어떠한 값을 넣어도 조건문이 성립하게 됩니다.

 

 

따라서 추가적으로 값에 근사한 값을 찾는 Upper Bound 와 Lower Bound 의 활용이 필요합니다.

 

 

 

Upper Bound

해당하는 조건이 처음으로 성립하는 값의 초과하는 값을 나타냅니다.

 

찾는 조건 : 3

 

[ 1, 2, 3, 3, 3, 4, 5, 6 ,7 ,8]

 

위 경우에 Upper Case 는 "4" 가 됩니다.

 

코드는 다음과 같습니다.

 

 

 

* 이분 탐색 (Binary Search) 와 차이점

 

1) while 조건이 < 로 바뀐다. ( start < end )

2) end = mid 로 +1 을 하지 않는다. ( 조건문에 따라서 달라짐 )

3) 끝으로 end 를 return 한다.

 

 

Lower Bound

해당하는 조건이 처음으로 성립하는 값을 나타냅니다.

 

찾는 조건 : 3

 

[ 1, 2, 3, 3, 3, 4, 5, 6 ,7 ,8]

 

코드는 다음과 같습니다.

 

* Upper Bound 와 다른 점은 nums[mid] <= target 에서 < 로 조건문이 바뀝니다.

 

 

 

위 문제에서는 Lower Bound 값을 찾는 것이 정답이 되겠습니다.

 

[ 1, 2, 3, 4 ... 48, ... , Int.max ]

 

 

정답 코드