[알고리즘/Algorithm] 파라메트릭 서치(Parametric Search) / BOJ 2110 공유기 설치

안녕하세요:)

이번에는 이전에 정리했던 이분탐색의 확장 개념인 파라메트릭 서치를 공부해 정리해보려고 합니다.

 

이분탐색 포스팅이 궁금하신 분들은 이 링크의 포스팅을 먼저 확인해보시길 추천드립니다!

http://melodyblue.tistory.com/40

[알고리즘/Algorithm] 이분 탐색(이진 탐색) / Binary Search Algorithm 이론 정리 및 예제 풀이

 

그럼 이제 파라메트릭 서치를 공부하고 예제도 풀어보겠습니다 :) ㅋㅋㅋ

---

파라메트릭 서치(Parametric Search)

---

파라메트릭 서치란, 

이분탐색의 확장 개념으로, 조건을 만족하는 값 중 최적의 값을 탐색하는 알고리즘 입니다.

즉,

조건을 만족하는 값들 중, 최대/최소 값을 찾는 과정을 이분 탐색으로 수행하는 알고리즘 기법

 

보통 문제에서 답이 될 수 있는 값의 범위가 정수 구간으로 주어지고,

그 값을 기준으로 "조건을 만족하는가?"를 판단할 수 있다면 이 기법이 적용됩니다.

 

🔹 이분 탐색과의 비교

그렇다면 이분 탐색과의 차이점은 무엇인지 비교 & 정리 해보면 다음과 같습니다.

구분	이분탐색(Binary Search)	파라메트릭 서치(Parametric Search)
핵심 목적	특정 값 찾기(존재여부)	조건 만족하는 "최적 값" 찾기
탐색 대상	정렬된 배열의 값	특정 조건을 만족하는 "값의 범위"
사용 방식	값 비교(정렬 기준)	조건 함수(check)를 통해 YES/NO 판별
결과	값 존재 여부 / 위치(인덱스)	조건을 만족하는 최대값 or 최소값
예시	수 찾기, 카드 찾기	예산 분배, 공유기 설치, 나무 자르기
공통점	low, high, mid를 사용한 이분탐색의 구조를 그대로 사용

 

즉, '해당 값을 찾으세요' 는 이분탐색, 

그리고 이분 탐색을 활용하여 '조건을 만족하는 최대/최소값을 찾으세요'는 파라메트릭 서치로 해결할 수 있습니다.

 

결국 파라메트릭 서치가 이분탐색의 확장해 활용하는 알고리즘 기법이라고 할 수 있습니다.

 

추가로, 문제의 예시로서 비교하자면 아래와 같이 표현할 수 있습니다.

 

🔹 이분탐색의 예시

배열 = [1, 3, 5, 7, 9]
Q: 값 5가 배열에 존재하는가?

* mid 값을 직접 배열의 값과 비교

* 값 자체를 찾는 게 목적

 

🔹 파라메트릭 서치의 예시

나무를 원하는 만큼 자를 수 있는 최대 높이를 구하시오.
-> 높이(Mid)를 기준으로, 자른 나무 길이의 총합이 목표 이상인가?

* mid를 정답 후보 값으로 설정하고,

* "조건을 만족하는가?" 만 판단 (YES/NO)

 

📝 정리

• 파라메트릭 서치는 이분 탐색을 문제 해결에 응용한 전략입니다.
• 기본 로직은 똑같지만 문제 해결 목표가 다르기 때문에 별도로 분류합니다.
• 많은 코딩 테스트 문제에서는 파라메트릭 서치를 잘 활용할 수 있는가? 를 평가하는 경향이 있습니다.

---

파라메트릭 서치 시간 복잡도

---

🔹 시간복잡도 분석

1. 전체 탐색:

log(최대값 - 최소값)

• 가능한 거리 범위에서 이분탐색 수행
• → log(max - min)

2. check 함수:

• 보통 선형 순회 (집/나무/사람 수만큼)
• → O(n) 

✅ 최종 시간 복잡도

O(N logM)

• N: 입력 크기 / f(n) 으로 표현하기도 함, check(mid)함수 1회 호출 시간
• M: 탐색 범위(정답이 될 수 있는 최대 범위), (max - min)

 

🔹 시간복잡도 증명

O(logX * f(N)) 일 때.

1. 이분탐색 부분: log X

: 정답 후보의 범위가 [low, high]라면 이진 탐색은 최대 몇 번 반복될지 입니다.

반복횟수 = log_2(high - low + 1) = log_2 X
* log_ : _다음의 숫자가 밑

따라서 이진 탐색의 반복 횟수는 O(logX)입니다.

 

2. 조건 확인 함수: check(mid): f(N)

: 매번 mid 값을 기준으로 조건을 판단해야 하므로, check(mid)함수가 O(N), 또는 O(N logN)일 수 있습니다.

- check 함수가 입력한 배열을 한 번 순회 : O(N)

- check 함수가 정렬 후 조건 판단: O(N log N)

   ; 내부에 정렬, 세그먼트 트리, 우선순위 큐, 이분탐색 등이 사용되면 O(N log N) 또는 O(log N)이 될 수 있습니다.

 

따라서 정리하자면,

🔹 최종 시간 복잡도

O(log X) * O(f(N)) = O(f(N) * log X)

가 됩니다.

---

예제 문제 풀이: BOJ 2110 공유기 설치

---

* 예제 문제: BOJ 2110 공유기 설치

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

 

🔹 문제 설명

N개의 집에 C개의 공유기를 최대 거리를 두고 설치하는 문제입니다.

이 때, 집은 수직선 위에 겹치지 않게 위치합니다.

 

🔹 해결과정

1. 정답 범위 설정

구하는 것은 "공유기 사이 최대 거리"입니다.

-> 정답 범위 = 거리 범위 가 됩니다.

집의 좌표가 같은 경우는 없으므로 최소 거리는 1이고, (left)

최대 거리는 주어진 집의 좌표 차이의 최대이므로 정렬된 좌표 중 0번째 인덱스의 좌표와 n-1번째 인덱스의 좌표 차이 (right)

 

2. 정답 탐색

mid로 설정한 거리를 기준으로 C개가 설치 가능한 지 탐색합니다.

- 만약 현재 거리로 C개 이상 설치가 가능하다면, 더 먼 거리 (인접한 공유기의 최대 거리를 찾는 문제이므로)가 가능한 지 탐색합니다.

- 만약 현재 거리로 C개 이상 설치가 불가능하다면, 더 짧은 거리로 C개가 설치가 가능한 지 탐색합니다.

 

🔹 소스첨부 & 설명

 

* 공유기 최대 거리 탐색

long left = 1;
long right = house[N - 1] - house[0];
long answer = 0;

while(left <= right) {
    long mid = (left + right) / 2;

    if(checkHouse(house, mid, C)) {
        answer = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

C개 설치가 가능할 경우: answer에 현재 값을 저장해줍니다. 탐색 종료 시 바로 print 해주기 위함.

left를 mid + 1로 바꿔 탐색하는 거리를 더 긴 거리 범위(mid + 1 ~ right)로 바꿔줍니다.

C개 이상 설치가 가능하다는 말은, 정답이 될 수도 있지만 보다 넓은 거리에서도 C개가 설치가 가능한 지 확인이 필요하기 떄문입니다.

C개 설치가 불가능: right = mid -1로 바꿔 탐색하는 거리를 더 짧은 거리 범위로(left ~ mid -1)바꿔줍니다.

C개 설치가 불가능 하다는 말은 공유기 사이의 거리가 너무 멀어 범위 안에 C개를 설치할 수 없다는 의미이기 때문입니다.

 

* check 함수

public static boolean checkHouse(int[] house, long dist, int C) {
    int cnt = 1;
    int lastInstalled = house[0];

    for(int i=0; i< house.length; i++) {
        if(house[i] - lastInstalled >= dist) {
            cnt++;
            lastInstalled = house[i];
        }
    }

    return cnt >= C;
}

단, 여기서 left, right, mid는 거리 값의 연산이 필요하므로 long으로 선언해주었습니다.

* long을 쓰는 이유

- 좌표값 자체는 1,000,000,000 -> int 가능

- 좌표차이(distance), 탐색 변수(mid, left, right)는 int 범위 내 이지만,

다른 문제로 확장하게 되면(곱셈, 누적합 등) long으로 안전하게 처리하는 습관을 들여두는 것이 좋습니다.

(이 이슈로 예전에 많이 틀렸었거든요.. 😂)

- 특히 입력 N이 크고 연산이 반복되는 경우 int 오버플로우를 방지할 수 있습니다.

 

'가장 인접한' 공유기 사이 거리의 최대이므로 distance보다 크거나 같을 때 설치가 가능합니다.

return 부분은 C개 이상의 공유기를 설치할 수 있는 지 여부만 확인하면 되므로 설치한 공유기 갯수가 아닌 가능 여부만 리턴해주었습니다.

 

🔹 전체 소스 코드

전체 소스코드는 아래 깃헙에서 확인하실 수 있습니다 :)

: https://github.com/hwlee0103/algorithm-java/blob/master/BOJ/src/baekjoononline/binarysearch/gold/boj2110AggressiveCows.java

algorithm-java/BOJ/src/baekjoononline/binarysearch/gold/boj2110AggressiveCows.java at master · hwlee0103/algorithm-java

 

이상으로 '파라메트릭 서치' 알고리즘을 활용한 BOJ 2110 공유기 설치를 풀어보았습니다.

'최대 범위', '최소 범위'를 탐색해야하는 이분탐색 문제의 경우 헷갈리기 쉽더라고요!

이번 기회에 예제랑 같이 풀이해보았습니다 ㅎㅎ

---

이렇게 이분 탐색의 심화 알고리즘인 파라메트릭 서치도 정리해보았습니다.

그동안 뭔가 '이분탐색 활용'문제를 풀 때 마다 '최대값/최소값을 ~' 이러는 문제는 이상하게 이분 탐색을 공부했어도 어렵고 와닿지 않는 부분이 많았습니다.

알고보니 '파라메트릭 서치'가 이분 탐색의 활용 유형으로 위와 같은 문제를 푸는 데 쓰인다는 것을 이번에 알았습니다.!

저처럼 이분탐색의 활용에 어려움이 있으셨다면 참고가 되셨으면 좋겠네요 !:)

 

그럼 다음에도 도움이 될 수 있도록 열심히 공부해오겠습니다 ㅎㅎ