[Java] 파라매트릭 서치(Parametric Search) 알고리즘

파라매트릭 서치(Parametric Search)는 바이너리 서치와 매우 유사합니다. 차이점은 최적화 문제를 결정문제로 바꾸어 푸는 것입니다. 원하는 조건을 만족하는 가장 알맞는 값을 특정한 오차범위 이내에서 알고 싶은 경우에 사용을 합니다.

• 바이너리 서치 : 배열에서 중앙값이 가리키는 값이 내가 찾는 값인지가 중요
• 파라매트릭 서치 : 원하는 조건을 만족하는 가장 알맞는 값을 찾는 것

동작과정

1. 데이터를 정렬한다.
2. 범위를 반씩 좁혀간다.
3. S 와 E 가 같을때 까지 진행한다.

 

시간복잡도

바이너리 서치와 같은 O( log N ) 입니다.

 

참고사이트

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

파라매트릭 서치(Parametric Search)

https://en.wikipedia.org/wiki/Parametric_search

Parametric search - Wikipedia

 

기본코드

'#' 의 개수를 알아내는 문제

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static char[] arr;
    
    static int parametricSearch(int s, int e){
    	
    	int maxIndex = -1;
    	
    	while(s<=e){
    		int mid = (s+e)/2;
    		char mVal = arr[mid];
    		
    		if (mVal == '#') {
                if (maxIndex < mid) maxIndex = mid;
                s = mid + 1;
            }
            else {
                e = mid - 1;
            }
    	}
    	
    	return maxIndex;
    	
    }
    
    public static void main(String[] args) throws IOException {      
    	
    	String str = "#######___";
   		arr = str.toCharArray();
  		
   		int cnt = parametricSearch(0, arr.length-1) + 1;
    		
   		bw.write(cnt+"\n");
    	
        br.close();
        bw.close();        
    }
}