[알고리즘] 파라메트릭 서치(Parametric Search)에 대해 알아보자!

본 포스팅에서는 파라메트릭 서치(parametric search)에 대해 알아봅니다.

📚 목차

1.  파라메트릭 서치란?
2.  파라메트릭 서치는 언제 사용하면 좋을까?
3.  파라메트릭 서치와 이진 탐색 간의 차이점
4.  파라메트릭 서치의 동작 과정
    4.1.  파라메트릭 서치 예시
    4.2.  파라메트릭 서치의 시간 복잡도

1.  파라메트릭 서치란?

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 풀어 나가는 기법입니다. 여기서 결정 문제란 'yes' or 'no', 즉, '예' 또는 '아니오'로 답하는 문제를 말합니다. 파라메트릭 서치는 주로 특정 조건을 만족하면서 동시에 가장 적합한 변숫값을 찾아나가는 문제에서 활용되며, 이진 탐색(Binary Search)을 이용하여 구현합니다. 예를 들어, 특정 조건을 만족하는 가장 큰 값을 구하는 최적화 문제에서 이진 탐색을 통해 적합한 해(solution)의 범위를 절반씩 좁혀 나갈 수 있습니다.

2.  파라메트릭 서치는 언제 사용하면 좋을까?

앞서 파라메트릭 서치 문제는 이진 탐색을 활용해 해결할 수 있다고 했습니다. 이진 탐색 알고리즘은 입력 데이터가 많거나(e.g., 1,000만 개 이상) 탐색 범위의 크기가 매우 넓을 때(e.g., 1,000억 이상) 효율적으로 문제를 해결할 수 있는 방법입니다. 파라메트릭 서치 역시 마찬가지로 입력 데이터가 많거나 탐색 범위의 크기가 매우 넓을 때 사용하면 좋습니다.

3.  파라메트릭 서치와 이진 탐색 간의 차이점

그렇다면 파라메트릭 서치와 이진 탐색 간의 차이점은 무엇일까요? 바로 결정 문제냐 아니냐입니다. 파라메트릭 서치는 특정한 조건을 만족하는 해(solution)를 찾을 때 결정 문제를 해결해 나갑니다. 즉, 특정 조건을 만족하느냐(yes) 혹은 만족하지 않느냐(no)에 따라 해의 범위를 좁혀 나가는 방법입니다.

4.  파라메트릭 서치 동작 과정

이제 파라메트릭 서치의 동작 과정에 대해 알아봅니다. 파라메트릭 서치는 이분 탐색을 기반으로 구현하기 때문에 리스트 내 특정 값을 찾기 위해 시작 인덱스, 중간 인덱스, 마지막 인덱스를 사용합니다. 구체적인 동작 순서는 아래와 같습니다. 예제없이 풀어서 설명하다 보니 이해가 쉽지 않으실 수 있습니다. 아래에 예제와 함께 살펴보시면 쉽게 파라메트릭 서치의 동작 과정을 이해하실 수 있을 거로 생각합니다.

 

1️⃣ 시작 인덱스와 마지막 인덱스 사이의 중간 값에서 소수점 이하를 버려 중간 인덱스를 정합니다.

2️⃣ 중간 인덱스에 해당하는 값을 활용했을 때 문제에서 주어진 조건을 만족하는지 여부를 확인합니다. 조건에 만족하지 않는다면 시작 인덱스 또는 마지막 인덱스를 수정하여 조건을 만족하는 중간 인덱스를 구합니다.

3️⃣ 조건을 만족한다면 2️⃣에서 구한 값이 최적의 해인지 여부를 확인합니다. 최적의 해라면 동작을 중단합니다.

4️⃣ 문제에서 주어진 조건을 만족하며 최적의 해를 구할 때까지 1️⃣~ 3️⃣ 과정을 반복합니다.

4.1.  파라메트릭 서치 예시

예를 들어, 아래 그림 1 과 같이 사람마다 고유 번호가 있는 10명의 사람이 성적에 따라 오름차순 정렬되어 있다고 가정해 보겠습니다. 여기서 "학점이 A(4.0) 이상"을 결정 문제의 조건이라고 하겠습니다. 해당 조건인 A 학점을 받은 사람 중 성적이 가장 낮은 사람을 찾는 문제를 파라메트릭 서치 기법으로 풀어보겠습니다.

 

그림 1.  파라메트릭 서치 동작 예시

 

(1) 먼저 시작점인 1과 끝점인 10의 중간점은 \(\frac{(1+10)}{2} = 5.5\) 에서 소수점 이하를 버린 5입니다. 중간점이 조건을 만족하는지 확인합니다(그림 2 참고). 편의상 시작점과 끝점은 녹색으로, 중간점은 파란색으로 표현하겠습니다. 중간점인 5가 조건을 만족하지 않는다면, 이미 1부터 10번까지의 사람이 성적 순으로 정렬되어 있다는 점에서, 사실상 5번을 포함해 번호가 낮은 사람들에 대해서는 조건의 만족 여부를 검증해 볼 필요가 없습니다.

 

그림 2. 파라메트릭 서치 동작 과정1

 

(2) 아래의 그림 3 과 같이 검증이 불필요한 사람은 회색으로 표현하겠습니다. 이제 시작점은 6, 끝점은 여전히 10이기 때문에 중간점은 8이 됩니다. 이번에는 중간점 8번 사람이 학점이 A 이상이라고 답했습니다. 따라서 끝점은 중간점 한 칸 앞인 7이 됩니다.

 

그림 3.  파라메트릭 서치 동작 과정2

 

(3) 마찬가지로 8번 사람이 A 학점 이상이며 9번, 10번 사람은 8번 사람보다도 성적이 높기 때문에 8반 사람 이후로는 학점을 물어보지 않아도 됩니다(그림 4 참고). 이제 끝점을 중간점의 한 칸 앞인 7로 옮기면 새로운 중간점은 시작점과 같은 6이 됩니다. 중간점에 해당하는 사람이 A 학점 이상이라고 답했기 때문에, A 학점이면서 성적이 가장 낮은 사람은 6번 사람임을 알 수 있습니다. 만일 6번이 A 학점이 아닐 경우에는 7번 사람의 학점도 알 수 없기 때문에 한 번 더 학점을 물어봐야 합니다.

 

그림 4.  파라메트릭 서치 동작 과정3

 

4.2.  파라메트릭 서치의 시간 복잡도

이진 탐색은 시작, 중간, 끝 인덱스를 활용하며 탐색 횟수별로 확인하는 데이터의 개수가 절반씩 줄어들기 때문에 시간 복잡도가 \(O(logN)\) 입니다. 마찬가지로 파라메트릭 서치 역시 \(O(logN)\) 의 시간 복잡도를 갖습니다.

📚 참고할 만한 포스팅

1.  [알고리즘] 순차 탐색(Sequential Search)에 대해 알아보자!(+Python 구현)
2.  [알고리즘] 이진 탐색(Binary Search)에 대해 알아보자!(+Python 구현)

---

포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 즐거운 하루 보내시길 바랍니다 :)

고맙습니다.