파라메트릭 서치 개념 정리

코테 문제를 풀게 되면 최댓값, 최솟값을 구해야하는데 변수의 볌위가 터무니 없이 넓어서 ( <= 1e9) 이걸 어떻게 제한 시간내에 동작시키나 하는 문제들이 있다. 이러한 문제를 풀기 위한 방법이 파라메트릭 서치이다.

 

목차

1. 파라메트릭 서치 개념

2. 주의 사항

3. 연관 문제 풀이 링크

 

 

1. 파라메트릭 서치 개념

파라메트릭 서치는 최적화 문제를 결정문제로 바꿔서 이를 이분탐색으로 활용하여 문제를 푸는 방식을 말한다.

말이 좀 어렵다. 최적화 문제, 결정문제에 대해 짤막하게 정리해보겠다.

 

최적화 문제 = 최솟값 또는 최댓값을 구하는 문제를 일컫는다. 

'리스트에서 최댓값을 구하여라', ' A에서 B 로 갈 수 있는 최소 이동 거리를 구하여라' 등이 이에 해당한다.

 

결정문제 = True 또는 False를 구하는 문제이다.

'리스트에서 20 이상을 넘는 수가 존재하는가' , 'A에서 B로 이동할 때, 이동거리가 14 이하인 방법이 존재하는가?' 등이 이에 해당한다.

 

다시 정리를 해보자면, 파라메트릭 서치는 최적화 문제를 결정 문제로 변환하고, 이분탐색으로 조절하는 값을 결정문제에 넣어서 true, false를 반환하도록 한다. 이를 반복해서 최적의 답을 찾게 된다.

 

 

최적화 문제 optimize를 , 결정문제 decision으로 변환했을 때, 파라메트릭 서치가 동작하는 과정을 표현하면 아래와 같다

 

 

decision 의 결과에 따라 값을 큰쪽으로 이동시키거나 작은쪽으로 이동시키면서 최적의 답안을 구한다. true, false에 따라 진행하는 방향은 문제마다 다르다.

 

 

2. 주의 사항

파라메트릭의 개념에 대해서 살펴보았다. 이제 주의해야할 점 2가지를 알아보자

 

2가지 주의사항

1. 결정문제 정의 방식

2. 결정문제 시간복잡도

 

 

1. 결정 문제 정의 방식

첫번째는 결정문제를 어떻게 정의해야하는지이다. 

decision(x) 라는 함수를 정의할 때, 단순히 'x 와 같은가?' 로 정의하는 것이 아닌 ' x 이상인가?' 'x 이하인가?' 이런식으로 방향성이 있어야한다. decision 함수의 결과값에 따라 어느 방향으로 이분탐색을 할지를 정해야하는데 단순히 'x 와 같은가?' 로 표현하는 경우 어느 방향으로 진행해야하는지 알 수 없기 때문이다. 

 

2. 결정문제의 시간복잡도

두번째로는 변환한 결정문제의 시간복잡도를 고려해줘야한다. 우리는 이분탐색을 하면서 결정문제에 값을 대입하기 때문에 전체 시간복잡도를 계산하면 아래와 같다.

 

전체 시간복잡도 = O(log n) x (결정문제의 시간복잡도) 

 

이분탐색에 소요되는 시간이 O(log n) 이기 때문에 이를 고려해서 전체 소요시간이 제한시간내에 동작할 수 있도록 결정문제의 알고리즘을 작성해야한다.

 

 

3. 연관 문제 풀이 링크

개념 및 주의 사항에 대해 정리를 했으나 이것만 보고 파라메트릭 서치가 무엇인지 정확히 알기는 어렵다. 

직접 문제를 풀어서 파라메트릭 서치가 무엇인지 느껴보자.

 

https://break-a-leg.tistory.com/26

백준 나무자르기 문제풀이

 

https://break-a-leg.tistory.com/27

백준 2110 공유기 설치 문제풀이