[C++ Algorithm] 매개 변수 탐색(Parametric Search)

저번 게시글에서는 이분 탐색(Binary Search)에 대해서 알아보았다. 

(https://m42-orion.tistory.com/69)

이번 게시글에서는 전에 이야기 했던 것처럼 매개 변수 탐색(Parametric search)에 대해 알아보고자 한다.

 

 

⭐️ 매개 변수 탐색(Parametric Search) 이란?

 

- 이진 탐색(Binary search)와 상당히 유사한 알고리즘

- Nimrod Megido에 의해 발명되었으며, 최적화 문제를 "결정 문제"로 풀 수 있는 알고리즘

- 시간 복잡도(Time complexity): O(log N)

 

---

⭐️ 매개 변수 탐색(Parametric Search)을 사용하는 시기

 

1. 결정 문제로 풀면 쉽게 문제를 풀 수 있을 때

 

2-1. 어떤 시점까지는 조건을 만족하지만, 그 후로는 조건을 만족하지 않는 경우. 조건을 만족하는 최대값 찾기

 

2-2. 어떤 시점까지는 조건을 만족하지 않지만, 그 후로는 조건을 만족하는 경우. 조건을 만족하는 최소값 찾기

 

 

---

⭐️ 매개변수 탐색(Parametric search)에서 중요한 문제 - 매개변수 param과 결정함수 fn(param)

 

매개 변수 탐색(Parametric search)에서는 크게 두 가지를 정하는 것이 중요하다.

매개변수 param과 결정함수fn(param)이다. 

 

 

1. 매개변수 param

매개변수 탐색(Parametric search)은 일반적으로 조건에 만족하는 최소값/최대값을 찾는 문제이다.

이 때, 검사하는데에 사용하는 매개변수를 param이라고 가정하자.

param은 검사 범위(left, right)에서의 중간 값이다. 즉, 해당 범위에서 (left + right) / 2가 param값이 된다.

 

 

2. 결정함수 fn(param)

fn(param)은 param이 조건을 만족하면 true를, 만족하지 않으면 false를 반환하는 함수이다.

반환 값에 따라서 검사 범위를 변경하게 된다.

---

 

param의 범위는 연속이어야 하는데, fn(param)의 값이 false->true로 전환, 혹은 true->false로 전환하는 부분이 생긴다.

이 때, true를 반환할 때의 param이 우리가 찾고자 하는 min/max 값이다.

결정함수 fn(param)의 결과에 따라서 검사 범위를 변경한다.

 

---

⭐️ 결정 함수의 구현

 

위의 결정 함수 fn(param)의 설명에서

fn(param) : param이 어떤 조건을 만족하면 true 반환, 만족하지 않으면 false 반환

이라고 이야기 했다.

 

"어떤 조건을 만족"하는 것은 param의 값에 따라서 문제에서 주어진 조건을 만족하는가를 묻는 것이다.

따라서 "어떤 조건"이 무엇인지 알고 싶다면, 문제에서 원하는 조건을 알아봐야 한다.

 

---

⭐️ 매개 변수 탐색(Parametric Search) 작동 방식

 

[조건을 만족하는 최대값을 찾을 때]

 

1) 배열 가운데 위치한 x를 결정 함수에 대입해 조건을 만족하는지 알아본다.

2) 조건을 만족한다면 검사 범위를 x보다 큰 쪽으로 설정.

   조건을 만족하지 않는다면 검사 범위를 x보다 작은 쪽으로 설정.

3) 1~2번을 살펴볼 배열이 남아있지 않을 때까지 반복.

 

 

조건을 만족하는 최소값을 찾고자 할 때에는 최대값을 찾았을 때와 반대로 실행하면 된다.

 

---

⭐️ Binary search와 Parametric search의 비교

 

[공통점]

두 알고리즘 모두 시간 복잡도가 O(log N)이다.

 

[차이점]

원하는 값을 찾았을 때 1) binary search는 위치 반환 후 함수를 종료한다.

                              2) parametric search는 살펴볼 배열(범위)가 없을 때까지 반복한다.

 

 

---

⭐️ 문제 예시: 1654 - 랜선 자르기

 

[문제 링크 & 설명]

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

문제를 간단히 정리해보자.

1) K개의 랜선을 가지고 있고, 랜선의 길이는 다르다.

2) K개의 랜선을 길이 x로 잘라서, 랜선을 N개 만드려고 한다.

3) 이 때, 길이 x로 자르고 남은 랜선은 버려야 한다.

4) N개보다 많이 만드는 것 또한 N개를 만드는 것으로 본다.

5) 이 때, x의 최대 길이를 구하시오.

 

 

 

[문제 해결 방법]

이분탐색&매개변수탐색으로 풀 수 있는 문제이다. K개의 랜선을 길이 x로 자를 때 N개를 만들어야 한다.

위에서 매개변수탐색에서 중요한 2가지가 있다고 했다. 첫 번째로는 매개변수 param이고, 두 번째는 결정함수 fn(param)이었다.

 

 

우선 매개변수 param을 정해보자. 이 문제에서 매개변수는 무엇일까?

바로 우리가 만드려고 하는 최대 랜선의 길이. 즉 x가 매개변수이다.

x의 길이는 검사범위에서의 중간 값(mid)이고, 결정함수의 결과에 따라서 x를 늘리고 줄이면서 확인하게 될 것이다.

 

길이 x의 범위를 생각해보자.

최소값과 최대값은 무엇일까?

랜선을 자를 수 있어야 하기 때문에, 최소 길이는 1일 것이고(0보다 커야 함), 최대 길이는 k개의 랜선들 중 제일 긴 길이일 것이다.

 

 

다음으로 결정함수 fn(param)을 정해보자. 이 문제에서 결정함수는 무엇일까?

문제를 다시 확인해보면, "K개의 랜선을 각각 길이 x로 잘랐을 때, N개의 랜선을 만들 수 있어야 한다"고 이야기하고 있고, 이를 결정함수로 설정할 수 있다.

위의 조건을 만족하면 true를, 만족하지 않으면 false를 반환하면 된다.

 

고로 K개의 랜선을 각각 길이 x로 나눈 몫을 모두 더한다.

이 값이 n보다 크거나 같으면 조건을 만족하는 것이기 때문에 true를 반환하고, 이 값이 n보다 작으면 조건을 만족하지 못하기 때문에 false를 반환한다.

 

 

결정함수 fn(param)의 반환 값을 어떻게 활용할까?

true를 반환했다는 이야기는 랜선을 n개 이상 만들었다는 뜻이므로, 랜선의 길이 x를 좀 더 늘려봐도 된다.

따라서 중간 값(mid)의 값을 더 높여야 한다. 그러므로 low = mid + 1을 해준다.

 

false를 반환했다는 이야기는 랜선을 n개 미만으로 만들었다는 뜻이므로, 랜선의 길이 x를 줄여야 한다.

따라서 중간 값(mid)의 값을 더 낮춰야 한다. 그러므로 high = mid - 1을 해준다.

 

 

이런 방법으로 계속 진행하다가 low > high가 되는 순간, 즉 검사할 구간이 더 이상 남아있지 않는 경우 검사를 종료한다.

조건에 만족하는 값이 나와도 바로 종료하지않는 부분이 binary search와는 다른 양상을 띈다.

 

 

 

[전체 Code]

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>

#define INF 1000000001
using namespace std;

// 1654 - 랜선 자르기
int k, n; // 랜선의 개수, 잘라서 만들고자하는 랜선의 개수
vector<int> lan; // k개의 랜선을 저장할 vector


void input() {
    cin >> k >> n;
    lan.assign(k, 0); // vector 동적 할당

    for(int i = 0; i < k; ++i){
        cin >> lan[i];
    }
}

// 매개변수로 mid를 전달한다. k개의 랜선을 길이 mid(len)으로 잘라본다.
bool isPossible(int len){
    // 아직 랜선을 자르지 않았으므로 cnt를 0으로 초기화한다.
    int cnt = 0;

    // k개의 랜선을 확인하면서 길이 x로 잘랐을 때 총 몇 개의 랜선이 나오는지 계산한다.
    for(int i = 0; i < k; ++i){
        cnt += lan[i] / len;
    }

    // 랜선이 n개 이상 나온다면 true를, 그렇지 않다면 false를 반환한다.
    if(cnt >= n)    return true;
    else    return false;
}

void solve(){
    // 랜선의 길이를 정렬하여 최대값을 구할 수 쉽게 한다. (필수X, 입력을 받으면서 갱신하는 방법도 가능)
    sort(lan.begin(), lan.end());

    unsigned int left = 1, right = lan[lan.size() - 1];
    unsigned int result = 0;
    
    while(left <= right){
        // 매개변수 param은 검사 범위의 중간 값이다.
        unsigned int mid = (left + right) / 2;

        // n개 이상 만들 수 있다면, 자르는 길이를 더 늘려도 된다. 즉, mid를 올려도 된다.
        if(isPossible(mid)){
            result = max(result, mid);
            left = mid + 1;
        }
        // n개 이상 만들 수 없다면, 자르는 길이는 줄여야 한다. 즉, mid를 내려야 한다.
        else{
            right = mid - 1;
        }
    }
    cout << result;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solve();

    return 0;
}

 

---

참고 사이트

https://movefast.tistory.com/311

https://annajeong.github.io/algorithm/parametric/