[프로그래머스 코딩테스트 고득점 Kit] - 이분 탐색

[프로그래머스 코딩테스트 고득점 Kit] - 이분탐색

입국 심사 - level 3

문제

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

문제의 조건대로 시뮬레이션을 통해 최적해를 찾는 방법은 시간 제한 내에 문제를 해결할 수 없다는 것을 입출력의 제한사항으로 파악할 수 있다.

입국심사를 기다리는 사람의 최대 수가 $10^9$이라는 것을 고려한다면, $O(N)$으로도 해결하기 힘들다.

다른 관점에서 문제를 생각해보아야한다.

결정론적인 방법으로 생각해보자, 함수 $F(k)$ 를 다음과 같이 정의해보자.

$F(k)$ : $k$시간에 직원들이 최대로 처리할 수 있는 고객 수가 n명 이상인가? (true / false)

정의에 따라, $F(k)$는 단조함수의 형태를 가진다. 이는 $k$를 기준으로 값이 false -> true로 이분화 되기 때문이고, $F(k) = true \rightarrow F(k) = true$ 인 것이 자명하기 때문이다.

그렇다면 최적해가 존재할 수 있는 구간을 점차 줄여나가는 식으로 알고리즘을 작성해보자.

초기 단계에서 최적해가 존재할 수 있는 부근은 [1, long long 의 최대 범위] 인근인 것이 보장되므로 해당 범위의 중간 값($m$)을 $F(m)$에 대입한다. 해당 범위에서 true라면, 해당 시간으로 n명 이상의 고객을 처리할 수 있으므로 해당 $m$ 값은 후보해라고 볼 수 있다.

이 경우에 최적해를 찾기 위해 다음 탐색 구간을 [1, $m-1$] 로 잡고 탐색을 진행한다.

만약, 특정 범위 $[a, b]$ 에서 $F(k)$가 false라면 후보해를 찾기 위해 탐색 구간을 $[(a+b)/2, b]$ 로 설정하여 탐색을 진행한다.

해당 알고리즘이 최적해를 찾을 수 있는 이유는 단조함수에 대하여 정수 해를 수학적으로 bisection method를 적용하여 구할 수 있는 것에 정당성을 둔다.

알고리즘 관점에서 보았을 때, 문제를 결정론적으로 치환하여 최적해가 존재하는 구간을 근사적으로 찾아내는 과정을 parametric search 라고 한다.

#include <string>
#include <vector>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;

    long long left = 1, right = 1e18;
    while(left <= right){
        long long mid = (left + right) / 2;
        // mid 시간내에 직원들이 처리할 수 있는 최대 고객 수가 n명 이상인가?
        long long peopleCount = 0;
        for(const auto &t : times){
            peopleCount += mid / t;
        }
        if(peopleCount >= n){
            answer = mid;
            right = mid - 1;
        }
        else
            left = mid + 1;
    }

    return answer;
}

징검다리 - level 4

문제

문제에서 구하고자 하는 것이 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값들의 집합 중 최대 원소 인 것을 상기한 다음, n의 범위를 살펴본다.

$1 \leq n \leq 50,000$ 의 범위를 가지며, 시간 제한내에 문제를 해결하기 위해서는 $O(NlogN)$의 시간 이하에 문제를 해결할 수 있어야함을 시사한다.

생각해볼 수 있는 방법으로 greedy 한 방법이 있겠다. 그러나, 어떠한 기준으로 greedy하게 접근하더라도 추후의 선택에 따라 최적해가 변하는 것을 어렵지 않게 찾을 수 있다. $\rightarrow$ 최적 부분 구조 x

다음으로 생각해볼 수 있는 방법은 문제를 결정문제로 치환할 수 있는지에 대한 생각을 해보자.

특정 $k$를 기준으로 이분화 될 수 있게, $f(k)$를 아래와 같이 잡는다.

$f(k)$ : 각 지점 사이의 거리가 k 이상이 되기 위해서 제거해야하는 바위가 n개 이하(true/ false)

그렇다면 $f(k)$를 구하기 위하여 오름차순으로 바위의 좌표를 방문하면서 거리가 k미만인 거리마다 바위를 제거해준다면 모든 거리가 k이상인 것이 보장되고 이때 총 제거된 바위의 개수가 n+1개 이상이면 절대 $n$개의 바위를 제거하는 것으로 지점 사이의 거리의 최솟값을 k로 못 맞춘다는 것이 된다.

반대로 총 제거된 바위의 개수가 n개 이하 (π개) 라면, 모든 거리가 k이상인 것이 보장되고 지점 사이의 거리의 최솟값을 k로 잡았을 때, 지점 사이의 거리 ß(ß > k)에 대해서 바위를 n-π개 더 제거하는 것으로 문제의 최적해를 만들 수 있다는 것이 된다. n-π개의 바위를 더 제거하는 과정에서 거리의 최솟값이 k가 되도록 유지하면서 제거하는 것이 가능하다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    sort(rocks.begin(), rocks.end());
    int left = 1, right = 1e9;
    while(left <= right){
        int k = (left + right) / 2;

        int prevPos = 0, counter = 0;
        for(int i=0; i<rocks.size(); i++){
            if(rocks[i] - prevPos < k){ 
                counter += 1;
            }else{
                prevPos = rocks[i];
            }
        }
        if(counter <= n){
            answer = k;
            left = k + 1;
        }else{
            right = k - 1;   
        }
    }


    return answer;
}