처음 배우는 parametric search 이해해보기

1. parametric search

 

이분 탐색을 응용하여, "최적화 문제"를 "결정 문제(decision problem)"로 바꿔서 문제를 푸는 알고리즘

 

최적화 문제는 예를 들면 다음과 같다.

 

"f(x) = True가 되는 x의 최댓값을 구하세요"

 

이를 결정 문제로 바꾸면 다음과 같을 것이다.

 

"어떤 x에서 f(x) = True인가?"

 

가능한 모든 x에 대해 f(x)가 True인지, False인지 검사한다면, 최적화 문제를 결정 문제의 집합으로 바꾸어 해결할 수 있을 것이다.

 

모든 결정 문제의 값 중에서 True인 최댓값을 구하면 되니까

 

하지만 모든 결정문제를 다 해결하는 것은 당연히 비효율적

 

그러나 어떤 조건을 만족한다면, 위 과정을 효율적으로 해결할 수 있다.

 

x1 < x2이고, f(x2) = True이면 f(x1) = True라는 조건이다.

 

즉 f(x)가 정렬되어 있다면 이분탐색의 아이디어를 그대로 적용할 수 있을 것이다.

 

"임의의 값 x에 대하여, f(x)가 True인지 False인지 검사한다.

 

f(x)가 정렬되어 있다면, f(x)가 True일때, x 이하에서 f(x)도 전부 True이다.

 

f(x)가 False일때, x 이상에서 f(x)는 전부 False이다.

 

따라서 이분탐색을 하듯이 x에 대한 범위를 절반씩 줄여가며 O(logN)번의 결정문제로 최적화 문제를 해결하는 것이다.

 

설명을 보면 알 수 있듯이 함수 f를 잘 정의하는게 중요한것 같다.

 

결정문제로 어떻게 바꾸는지는 문제를 많이 풀면서 느끼는.. 체득의 영역

 

 

2. 예시로 이해하는 parametric search

 

n개의 섬과 m개의 다리가 있다.

 

다리마다 무게 제한이 있어서, 제한보다 무거운 차량이 지나간다면 다리가 무너진다.

 

0번 섬에서 n-1번 섬으로 이동할 수 있는 차량 무게의 최댓값을 구해라.

 

이 문제를 푸는 방법은 여러가지가 있지만, parametric search를 이용한 방법이 있다.

 

만약 무게가 x인 차량이 0번 섬에서 n-1번 섬으로 이동할 수 있다면, 당연히 x보다 가벼운 모든 차량도 0번 섬에서 n-1번 섬으로 이동할 수 있게 된다.

 

반대로 무게가 x인 차량이 이동할 수 없다면, 당연히 무게가 x보다 무거운 차량도 이동할 수 없게 된다.

 

그러므로 함수 f를 f(i) = 무게가 i인 차량이 0번 섬에서 n-1번 섬으로 이동할 수 있는지의 여부라고 한다면...

 

 

 

위와 같은 이분 탐색을 할 수 있는 True/False 배열의 형태가 된다.

 

제한이 1에서 10^9이라면, start = 1로 하고 end = 10^9+1로 해서..

 

True가 되는 마지막 위치를 찾는 upper bound를 수행하면.. 문제를 해결할 수 있겠네

 

최대 무게를 찾으라는 최적화 문제가 이분탐색 한방으로 해결하는 결정 문제가 된다

 

 

3. 연습문제

 

2512번: 예산 (acmicpc.net)

2512번: 예산

 

4. 풀이

 

알고리즘 복기를 해도 모르겠네..

 

아무튼 주어진 배열을 일단 정렬하고..

 

어떤 정수값 이하로는 배열 내의 값을 모두 합하고, 주어진 예산 제한 m에 대하여..

 

m - (합한 값)이 정수값 이상에 투자할 수 있는 예산인데..

 

여기서 정수 상한액을 어떻게 찾았냐면.. 결국 A[mid]와 A[mid+1] 사이에 있는 값중에서 가능한 최댓값

 

여기서 가능하다는 것은..

 

정수 상한액 이후로는 동일한 정수값을 부여할 것이고, 그 개수를 전부 합했을 때 m - (합한 값)을 넘어가면 안되잖아 이 말이다

 

아무튼 A[mid]와 A[mid+1] 사이에 있는 값중에서 가능한 최댓값을 binary search로 찾는다

 

이렇게 찾은 정수 상한액 x가 A[mid]와 A[mid+1] 사이에 있다면,

 

조건을 만족하면서 mid+1~end에 더 큰 x가 존재할 수 있다는 뜻이므로, 최댓값 answer를 갱신하고 start를 mid+1로 옮겨준다

 

하지만 x가 A[mid] 왼쪽으로 구해질 수도 있다. 그런 경우 정수 상한액 x가 존재할 수 없어서

 

end를 mid로 옮겨서 start~mid에서 재탐색을 수행

 

from sys import stdin

def binary_search(target,start,end,num):
    
    while start < end:
        
        mid = start + (end - start)//2

        if mid*num <= target:
            
            start = mid + 1
        
        else:
            
            end = mid
    
    return end - 1
    
def parametric_search(A,start,end,total,n):
    
    answer = 0
    
    while start < end:
        
        mid = start + (end - start)//2

        sub = total - sum(A[:mid+1])

        if n == mid+1:
            
            answer = A[-1]
            
            break
        
        x = binary_search(sub,A[mid],A[mid+1]+1,n-(mid+1))

        if x <= A[mid+1] and x >= A[mid]:
            
            if x > answer:
            
                answer = x

            start = mid + 1
        
        else:
            
            end = mid
    
    return answer

n = int(stdin.readline())

A = list(map(int,stdin.readline().split()))

m = int(stdin.readline())

A.sort()
    
answer = parametric_search(A,0,n,m,n)

if answer == 0:
    
    print(binary_search(m,1,A[0]+1,n))

else:
    
    print(answer)

 

이렇게 search 했을때, mid가 배열의 최대길이 n으로 이동하면.. 예산 m 이내로 모든 곳에 분배할 수 있다는 뜻이니..

 

A[-1]을 return하면 될 것이고

 

answer가 여전히 0이라면.. 주어진 배열 내에서 index가 0번으로 이동했다는 뜻이잖아..

 

그러면 A[0]-1을 return해야하나??

 

아니면.. A[0]가 1이면.. 1을 return해야하나??

 

그게 아니고 A[0], A[1], ... A[n-1]까지 모두 동일한 정수 상한액 x로 부여해야한다는 뜻이므로...

 

1부터 A[0] 사이에서 예산 제한 m 이내가 되도록 binary search로 x를 찾아줘야한다..

 

 

5. 깔끔한 풀이

 

와 근데 엄청나네...

 

가능한 "정수 상한액"은 0부터 주어진 배열의 최댓값

 

배열의 최솟값부터 배열의 최댓값이 아니라 0부터 배열의 최댓값인 이유는???

 

주어진 배열의 최솟값보다 더 적은 돈을 배정해야하는 경우가 있을 수 있다.

 

예를 들어..

 

3100 100 10050

 

이러면 최대 예산이 50인데 배열의 최솟값은 100이니까 100부터 100으로 검사해버리면 당연히 오답이지

 

from sys import stdin

def parametric_search(city,start,end,m):
    
    while start < end:
        
        #비용이 든 배열 city에서 중간 지점을 찾는다.
        #중간 지점이 "정수 상한액"
        mid = start + (end - start)//2

        total = 0

        #중간 지점 이후로는 정수 상한액 mid값을 더해주고
        #중간 지점 이전에는 해당 액수 c값을 더해주면
        for c in city:
            
            if c > mid:
                
                total += mid
            
            else:
                
                total += c
        
        #mid가 "정수 상한액"일때... 가능한지 아닌지 검사
        #배열 city가 오름차순이므로, 전체 비용이 예산보다 크다면...
        #start ~ mid-1에 정답이 있다
        if total > m:
            
            end = mid
        
        #전체 비용이 예산 이내라면...
        # mid ~ end에 정답이 있다
        else:
            
            start = mid + 1
    
    return start - 1

n = int(stdin.readline())

city = list(map(int,stdin.readline().split()))

m = int(stdin.readline())

city.sort()

print(parametric_search(city,0,city[-1]+1,m))

 

가능한 정수 상한액을 mid로 먼저 지정하고..

 

배열의 cost를 순회해서, mid보다 크면.. mid를 더해주고

 

mid보다 작거나 같으면 순회한 c를 더해주어서 

 

가능한 정수 상한액이 mid일때, 사용한 예산의 합을 total이라고 하자.

 

total이 제한 m 이내이냐? m보다 크냐?로 나눠서 이분탐색을 할 수 있을 것.

 

와 근데 지리긴하네.. 도저히 생각못했다

 

city가 오름차순 정렬되어 있어서.. mid가 커질수록 total도 커질 것이다

 

그리고 인덱스가 start가 아니고 start - 1을 return해야겠던데..?

 

인덱스가 힘드네..