Parametric Search(파라메트릭 서치) 알고리즘 개념

# Parametric Search(파라메트릭 서치) 알고리즘 개념

- Binary Search를 응용한 방법으로 기본적인 탐색 방법은 Binary Search와 비슷함

- 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것

- 원하는 조건을 만족하는 가장 알맞는 값을 특정한 오차범위 이내에서 알고싶은 경우 사용

- 임의의 값으로 계산 후 확인해가며 해를 구하는 방법 (Binary Search 사용)

# Binary Search vs Parametric Search

Binary Search: 배열에서 중앙값(middle)이 가리키는 값이 내가 찾는 값인지 중요

Parametric Search:  원하는 조건을 만족하는 가장 알맞는 값을 찾는 것

# 시간복잡도

Binary Search와 마찬가지로 O(logN)의 복잡도를 가지게 된다.

# Parametric Search를 사용할수 있는 조건

1) 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경우

2) (최소값을 구하는 경우) 최소값이 x라면, x이상의 값에 대해서는 모두 조건을 만족

3) (최대값을 구하는 경우) 최대값이 x라면, x이하의 값에 대해서는 모두 조건을 만족

# 참고사항

* 데이터는 정렬된 상태이면 좋지만, 정렬되지 않은 경우도 사용가능하다.

   - 데이터가 정렬되지 않은 경우에는 중간값을 설정 기준이 중요하다?? 

     (목적에 맞게 조건을 설정하는 것이 중요)

# SWEA 샘플 코드

import java.io.FileInputStream;
import java.util.Scanner;
 
public class ParametricSearch {
    static int K;
    static int N;
    static int low;             // 리본의 최소 길이
    static int high;            // 리본의 최대 길이
    static int mid;             // 리본의 중간 길이
    static int numRibbon;       // 중간 길이로 자른 경우 리본의 개수
    static int Answer;          // 리본의 최대 길이
    static int sizeRibbon[];    // K개 리본의 길이
 
    static void search() {
        // 중간 값을 구하기
        mid = low + (high - low) / 2;
        numRibbon = 0;
        // System.out.printf("[Before] low:%5d, mid=%5d, high=%5d, (high-low)/2=%5d,
        // numRibbon=%5d, Answer=%5d\n",
        // low, mid, high, (high-low)/2, numRibbon, Answer);
 
        // 중간값으로 나눠서 리본 개수를 구하기
        for (int i = 0; i < K; i++) {
            numRibbon += (sizeRibbon[i] / mid);
        }
 
        // 필요한 리본개수보다 같거나 많은 경우
        // - 리본의 최소 길이 = 중간길이 + 1
        // - 중간길이 > 현재 최대 길이
        // - 최대 길이로 설정
        // 필요한 리본개수보다 적은 경우
        // - 리본의 최대 길이 = 중간 길이 - 1
        if (numRibbon >= N) {
            low = mid + 1;
            if (Answer < mid)
                Answer = mid;
        } else {
            high = mid - 1;
        }
 
        // System.out.printf("[After ] low:%5d, mid=%5d, high=%5d, (high-low)/2=%5d,
        // numRibbon=%5d, Answer=%5d\n",
        // low, mid, high, (high-low)/2, numRibbon, Answer);
    }
 
    public static void main(String arg[]) throws Exception {
        System.setIn(new FileInputStream("C:\\java\\SW\\sample.txt"));
        Scanner sc = new Scanner(System.in);
 
        int T = sc.nextInt();
        for (int test_case = 1; test_case <= T; test_case++) {
            low = 1;
            high = 0;
            Answer = -1;
 
            K = sc.nextInt();
            N = sc.nextInt();
            sizeRibbon = new int[K];
 
            // 리본 길이의 최대값을 구하기
            for (int i = 0; i < K; i++) {
                sizeRibbon[i] = sc.nextInt();
                if (high < sizeRibbon[i]) {
                    high = sizeRibbon[i];
                }
            }
            // System.out.printf("%d: %d\n", test_case, high);
 
            while (low <= high) {
                search();
            }
            System.out.println("#" + test_case + " " + Answer);
        }
    }
}

# 관련 문제

[2110번] 공유기 설치 :: https://www.acmicpc.net/problem/2110

[1654번] 랜선 자르기 :: https://www.acmicpc.net/problem/1654

[2613번] 숫자 구슬 :: https://www.acmicpc.net/problem/2613

# 참고사이트

https://www.crocus.co.kr/1000

https://coderkoo.tistory.com/8

https://sarah950716.tistory.com/16

https://its2eg.tistory.com/entry/%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89Binary-Search%EC%99%80-%ED%8C%8C%EB%9D%BC%EB%A9%94%ED%8A%B8%EB%A6%AD-%EC%84%9C%EC%B9%98Parametric-Search