파라메트릭 서치(Parametric Search)

### 파라메트릭 서치 ###

: 원하는 조건(범위) 내에서 최대,최소 값을 찾는 문제  => 결정 문제

(이분 탐색으로 해결) (ex, ~한 것중에서 최대,최소 인 값을 찾으시오)

 

< 조건 >

1.

위의 개념에 만족 

2. 

최댓값 -> 최댓값보다 작은 값들이 조건을 모두 만족  

최솟값 -> 최솟값보다 큰 값들이 조건을 모두 만족 

3. 

정확한 값을 구할 수 있어야 한다. (무한대 x)

 

 

< 시간 복잡도 > 

O(조건함수(n) * logn)

 

 

< 풀이 >

1. 최댓/최솟값을 구하는 것을 기준으로 start, end(이분 탐색 기준)를 잡는다.

  (start = mid + 1, end = mid - 1이 값을 크/작 게 만드는 지 파악하기) 

 

2. 함수를 만들어 범위를 줄여 나가며 답을 구한다.

 

< 예시 코드 >

# 최댓/최솟값의을 얻는 것을 기준으로 만들기
start = house[1] - house[0]
end = house[-1] - house[0]

# 이분 탐색
while (start <= end):
    mid = (start + end) // 2 
    val = house[0]
    cnt = 0 

    # 범위를 정하기 위한 함수 
    for install in range(1,n):
        if house[install] >= val + mid:
            val = house[install]
            cnt+=1

    if cnt >= c:
    	# start = mid + 1 인 경우는 값을 크게 만드는 것 
        start = mid + 1 
        result = mid 
    
    else:
		# end = mid -1 인 경우는 값을 작게 만드는 것
        end = mid - 1

 

 

 

< 문제 >

-> 백준 2110번, 백준 1654번,  백준 2613번, 백준 2805번