Parametric Search란?
Parametric Search는 최적화 문제를 해결하기 위한 알고리즘 기법으로, 특정 값(예: 최대값, 최소값)을 찾기 위해 문제를 "결정 문제"로 변환하여 해결합니다. 이 과정에서 Binary Search를 활용하여 탐색 범위를 줄여가며 효율적으로 해를 찾아냅니다.
예를 들어, "주어진 예산으로 물품을 구매할 때 가장 비싼 물품 가격은 얼마까지 가능한가?"와 같은 문제에서 Parametric Search를 사용할 수 있습니다. 이 기법은 최적화와 결정 문제를 연결함으로써 복잡한 문제를 간단하게 해결할 수 있게 합니다.
Binary Search 와의 연관성
Parametric Search는 Binary Search의 확장판으로 볼 수 있습니다.
Binary Search는 정렬된 배열에서 특정 값을 찾는 데 사용됩니다. 예를 들어, [1, 3, 5, 7, 9] 에서 7의 위치를 찾는 문제를 해결합니다.
Parametric Search는 이 접근 방식을 더 일반화하여, 어떤 조건을 만족하는 최적의 값을 찾는 데 사용됩니다. 예를 들어, "최대 중량을 초과하지 않으면서 가장 무거운 화물을 선택하는 값"과 같은 문제를 해결합니다.
Binary Search가 정렬된 데이터를 탐색하는 데 초점이 맞춰져 있다면, Parametric Search는 "결정 함수"를 통해 가능한 범위를 효율적으로 좁혀가는 방식으로 최적의 값을 찾아냅니다.
Example
해당 예시는 BAEKJOON 1654 - 랜선 자르기 를 이용하였습니다.
당신은 802, 743, 457, 539 의 랜선을 4개 가지고 있고, 11개의 랜선을 각 랜선을 잘라서 동일한 크기이며, 가능한 최대 길이로 만들어야 한다. 이 상황에서 이 4개의 랜선을 조건에 맞게 11개의 랜선으로 만들 때 가능한 최대의 크기를 구해보자.
동일한 크기로 만들어야 하는 변수값을 x 으로 지정한다면, x의 범위는 1~802 이 가능하다. 즉 범위는 정해졌으며, 해당 범위 내에서 11개의 랜선을 만들 수 있는 최적의 값을 찾아야 한다.
- 해당 범위내에서 Binary Search 가 사용해.
401이라는 수치를 선정하고, 해당 수치를 기준으로 Parametric Search 의 결정 함수가 이용된다.
- 이 문제에서의 결정함수는, 각 랜선을
401이라는 값으로 나누기를 진행해 각 몫을 구해 전부 합한다. 그러면5라는 수치가 나오며 이 결과값은 5개의 랜선이 만들어 진다는 걸 뜻한다. 우리는 6개의 랜선이 더 필요하기 때문에 랜선의 길이를 좀더 줄여야 할 필요가 있다는 것을 알았으며,x가401의 길이보다 더 크거나 같으면 안된다는 것을 자연스럽게 알 수 있다.
- 그러면 다시 범위가
1~400으로 정해지며, 위의 과정을 똑같이 시행하면 된다.
- 만약
x가11개를 넘는 수치가 나왔다면 반대로, 랜선의 길이를 늘려야 하기 때문에 2번의 과정에서 범위 조정을 반대로 진행하면 된다.
그리하여, 정답은 각 랜선을 200씩 절단하면 11개의 랜선을 최대의 길이로 만들 수 있게 된다.
In Conclusion
Binary Search 는 정렬된 데이터 안에서 중간값의 개념을 이용해 범위를 지속적으로 줄여나가는 방법이며,
Parametric Search 는 문제에 맞는 결정함수를 올바르게 생성하여 입력된 Parametric 가 조건에 충족하지 않는다면, 결정함수 내부 로직에 의해 효율적으로 범위를 조절해나가는 방법을 뜻한다.
