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

 

매개 변수 탐색은 이분 탐색의 활용 버전입니다.

이분 탐색은 탐색을 통해 target 값을 찾는 알고리즘이었습니다.

그렇다면 매개 변수 탐색도 target 값을 찾는 또 다른 방법일까요? 아닙니다.

 

https://mengu.tistory.com/83?category=931463 

[Algorithm] 이분 탐색(Binary Search) 개념 및 코드(python)

 

 

 

📌 매개 변수 탐색(Parametric Search) 정의

 

매개 변수 탐색은 조건을 만족하는 값(target) 중에서도 최댓값 혹은 최솟값을 찾는 알고리즘입니다.

이분 탐색에선 'mid값이 target 값보다 큰가?'를 물어보며 배열을 나눴습니다. 매개 변수 탐색은 최적화 문제를 결정 문제로 바꿔서 해결하고자 합니다. 처음부터 최댓값을 찾기 위해 움직이는 것이 아니라 조건에 해당되는 것들을 쫓다보니 최댓값을 발견했다는 방식으로 푸는 것입니다.

 

 

 

좀 더 명확한 이해를 위해 탐색 과정(최댓값 찾기)을 보여드리겠습니다.

 

(1) 배열을 나눌 참/거짓 조건문을 만듭니다.

=> 000 조건을 만족하는가?

 

(2) 배열의 start, mid, end 값을 정하고, 탐색 함수에 넣습니다.

 

(3) 함수에선 mid 값이 조건이 부합하는지 판별합니다. 만약 부합한다면 오른쪽으로 mid를 옮기고, 부합하지 않는다면 왼쪽으로 mid를 옮깁니다.

 

(4) 이렇게 mid값을 계속 옮기며 마지막 하나의 값이 나올 때까지 반복합니다.

 

(5) 최종적으로 나온 수가 최댓값입니다.

 

 

 

 

🎨 매개 변수 탐색 과정 

 

 

 

 

 

🎨 바닐라 파이썬 코드

def check_condition(value):
	# 조건 검사
    return 참 또는 거짓


def parametric_search(array, start, end):
	while start + 1 < end:
    	mid = (start+end) // 2
    	if check_condition(mid):
        	start = mid						# 오른쪽으로 이동 ->
        else:
        	end = mid						# 왼쪽으로 이동 <-
   	return array[start]

배열과 처음, 끝을 매개 변수 탐색 함수에 넣습니다.

while 문을 통해 조건 비교, 이동을 반복하도록 했고, 마지막 하나가 남았을 때 멈춥니다.

return array[start]가 바로 조건을 만족하는 최댓값이 됩니다.

 

 

 

지금까지 이분 탐색의 응용 버전인 매개 변수 탐색에 대해 알아보았습니다.

개념을 배웠으니, 문제를 풀어보며 더 확실하게 이해하시길 바랍니다.

고생하셨습니다.

 

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

1654번: 랜선 자르기