[Algorithm] Parametric Search

🤖 Algorithm

---

🔵 Parametric Search

❗ 최적화 문제 -> 결정 문제로

ex)
특정 상황을 만족하는 최소 or 최대를 구해라
-> 최소 or 최대 후보 중에서 조건 만족하는 후보 찾기

1. 특정 조건을 만족하는 MAX or min을 구하는 문제
2. 기준점을 중심으로 좌우가 조건을 만족함 / 조건을 불만족함으로 구분되어야 함
3. 답이 정확한 값이 아님 -> 이산적 or 허용 오차 범위 존재

➡️ Binary Search로 문제 해결

🌟 mid를 어떻게 잡느냐가 핵심

ex)
프로그래머스 징검다리 문제

출발지점과 도착지점 사이에 바위 존재 -> 바위를 n개 만큼 제거
바위 간 거리의 최소값들 중에서 최대값을 찾는다

mid를 바위 사이 거리의 최소값으로 설정

1. mid보다 거리가 짧으면 바위 제거
2. 제거한 바위 개수가 n보다 크면 end->mid-1로 하여 mid 갱신
3. 제거한 바위 개수가 n이하이면 start->mid+1로 갱신 + answer=max(answer,min)

    int start=0;
    int end=distance; // 도착 지점
    
    while(start<=end)
    {
        // mid는 돌과 돌 사이 거리의 최소값
        int mid=(start+end)/2;
        int preRock=0;
        int cnt=0;
        
        for(int i=0;i<rocks.size();i++)
        {
           // 최소값 보다 작을 수 없음 -> 바위 제거
           if(rocks[i]-preRock<mid)
               cnt++;
            else
                preRock=rocks[i];
        }
        // 마지막 바위에서 도착지점까지 거리
        if(distance-preRock<mid)
            cnt++;
        
        if(cnt>n)
            end=mid-1;
        else
        {
            answer=max(answer,mid);
            start=mid+1;
        }
    }