[Algorithm] Parametric Search

HyunDong Lee·2022년 5월 19일
0

Algorithm

목록 보기
10/10
post-thumbnail

Parametric Search

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 푸는 것 입니다.

예를 들어 일렬로 나열된 숫자 중에서 키가 3이상인 값을 갖는 최소 인덱스 값을 계산해야 한다고 가정해봅시다. 각각의 크기는 크기별로 정렬되어 있고,

분류
인덱스0 1 2 3 4 5 6 7 8 9 10 11
1 2 2 2 2 3 3 4 4 4 5 5

만약 크기가 3이 넘는 사람은 키가 크다는 것이 증명되어 있다고 가정합시다.

앞에서 부터 탐색하면서 차례대로 크기가 3이상인지 확인한다면, O(N)의 시간 복잡도를 갖습니다. 하지만 파라메트릭 서치를 이용하여 최적화 문제를 결정 문제로 바꾸면 O(logN)의 시간 복잡도로 문제를 해결할 수 있습니다.

최적화 문제의 관점으로는 "크기가 3 이상인 가작 작은 인덱스"(최솟값의 관점으로 해석)
결정 문제 관점으로는 "키가 큰지 아닌지"를 물어보면 YES(키가 3이상), 키가 작다면 NO(3 이하) 두 가지 관점으로 나누어 생각할 수 있다.

그렇다면 쭉 나열된 숫자 중에서
l = 0, r = N-1사이에 중간부터 탐색을 하며 키가 큰지 작은지 물어볼 수 있다.

int parametricSearch(int start, int end){
	int mid;
    while(start <= end){
    	mid = (start+end)/2;
        if(arr[mid] > 3)
        	start = mid+1;
        else if(arr[mid] <= 3)
        	end = mid-1;
        else
        	break;
    }
    return mid;
}

mid 값이 최소인지 최대인지에 따라 코드가 조금 달라질 수 있다. 그것에 대한 문제는 아래 링크에 잘 정리가 되어 있기 때문에 참고하면 좋을 것 같다.
나중에 문제를 풀면서 이론을 좀 더 보완하자!

이분탐색 유의사항

0개의 댓글