1. Parametric Search 란?

최적화 문제를 여러 개의 결정 문제 + 이분 탐색으로 변환시키는 문제 접근 방법이다. 여기서 3가지 키워드가 나왔는데, 이분탐색이 뭔지는 많은 사람들이 알테니, 최적화 문제와 결정 문제에 대해 먼저 설명하고 가겠다.

(1) 최적화 문제

문제의 조건을 만족하는 해의 범주가 존재하고, 그 중에서 최적의 답(최소값, 최대값 등)을 구하는 문제를 말한다.

Thread Knots라는 문제를 예시로 들어보면, 해당 문제는 'n개의 매듭을 성공적으로 놓았을 때, 가장 가까운 두 개의 매듭 사이의 최대 거리를 출력하라'고 요구한다.
그렇다면, 여기서 가능한 해의 범주는 n 개의 매듭을 각 Thread에 성공적으로 놓는 모든 경우이고,
최적의 해는 가장 가까운 두 매듭 사이의 최대 거리일 것이다.

(2) 결정 문제

문제의 답을 YES or NO로 하는 문제를 뜻한다.
'엘리베이터 안에 15명이 들어갈 수 있는가?', '토요일은 주말인가?' 등이 이러한 결정 문제일 것이다.
이런 게 가능하려면, 문제 내부에 문제의 정답 여부를 결정 짓는 조건이 존재해야 한다.

(3) 소결

이제 두 문제 유형의 뜻을 알았다. Parametric Search는 최적화 문제 ➜ 여러 개의 결정 문제 +이분 탐색으로 바꾸는 문제 접근 방법이라고 했다. 이제는 어떻게 그렇게 변환할 수 있는지에 대해서 집중적으로 살펴 보자.

2. Parametric Search 과정

1️⃣ YES or NO 조건 을 만들어서 최적 해를 조건의 답 중 하나로 포함시키기
2️⃣ YES or NO 조건의 답이 단조적이어서 예측 가능한지 확인 (불가하면 Parametric Search 못 씀)
3️⃣ YES or NO 답의 범주 내에서 이분 탐색으로 답 찾기

하나씩 살펴보자.

1️⃣ `YES or NO` 조건 을 만들기 ➜ 최적 해를 조건의 답 중 하나로

해당 과정이 바로 최적화 문제를 여러 개의 결정 문제로 만드는 과정이다.
변환은 센스의 영역이긴 하지만, 이분탐색 문제를 많이 풀다보면 감이 온다. 여기서 중요한 점은 최적 해를 결정 문제 답 중 하나로 포함 시킬 수 있는가? 이다.

위의 Thread Knots를 예로 들어보면, 문제는 '가장 가까운 두 매듭 사이의 최대 거리를 구하라' 라고 했다.
이는 '모든 매듭 사이의 거리가 d 이상이 되는가?'로 변환 가능하다.
이렇게 변환이 가능한 이유는 처음 매듭을 놓았을 때, 가장 가까운 두 매듭 사이의 거리를 점진적으로 늘리다보면, 그 두 매듭이 더 이상 가장 가까운 매듭이 아니게 될 수 있다. 따라서 두 개의 점을 특정해서 보는 것은 소용이 없고, 모든 점에 대해서 최소 기준을 통과하는지 확인해야 한다. 그렇다면 '모든 매듭 사이의 거리가 d 이상이 되는가?'를 f(d)라고 한다면, 이 f(d)의 d의 최대값이 바로 Thread Knots문제의 답이 될 것이다.

이제 최적해가 결정 문제의 매개변수 중 하나로 포함되므로 1️⃣ 은 성공적으로 마쳤다. (결정 문제의 매개 변수를 찾는 풀이 방식이라 이름이 Parametric Search (매개 변수 탐색) 이다.)

2️⃣ `YES or NO` 조건의 답이 단조적이어서 예측 가능한지 확인

결론: 단조 ➜ 예측 가능 ➜ 이분탐색 쓸 수 있음

단조란? ✨

수학에서 단조라는 말의 의미는 수열이 증가하거나 혹은 감소하는 하나의 규칙(mono)만을 가진다는 말이다. 즉 오름차순이나, 내림차순으로 정렬된 상태를 의미한다. 답이 TRUE 아니면 FALSE 밖에 없는 결정문제 SET에서 단조적이라는 것은 무엇을 말하는 것일까?
'결정 문제의 반환 값들이 단조적이다. ' *이라는 말은, *'TRUE = 0, FALSE = 1로 보았을 떄, 내림차순 혹은 오름차순이 성립한다.'는 의미이다.

결정문제 반환 SET이 단조적인 것이 왜 중요한가? ✨

결정문제 반환 SET이 단조적인 것이 중요한 이유는, 답이 되는 매개 변수의 위치를 예측할 수 있기 때문이다. 우리는 결정문제 SET을 구한 후, 이분 탐색을 활용해, 답이 되는 매개 변수를 찾는다. 이분탐색을 활용할 수 있는 Data Set의 전제 조건은 무엇이었는가? 바로 정렬된 상태이다.
정렬된 상태가 필요한 이유도 똑같이 '답이 존재하는 영역을 예상할 수 있게 만들어줘서' 이다. 현재 가리키고 있는 MID값이 TARGET보다 작다면, MID보다 작은 값은 어짜피 답이 안되므로 확인할 필요가 없다. 따라서 오름차순으로 정렬된 Data Set에서는 MID보다 작은 값 (영역의 절반)을 값 후보에서 제외시킬 수 있었다.

추후, 답이 되는 매개변수를 찾기 위해 이분탐색 과정이 필수적이므로 결정 문제 또한, 정렬된 Data Set 처럼 단조적인 성질을 가지고 있어야 한다. Thread Knots 예시를 계속 보자. 위에서 f(d) = 모든 Thread에 대해서 매듭 사이의 거리가 d 이상이 되는가?로 두었다. 일단 f(d)를 구하는 것은 차치 해두고, 이것의 결과를 얻었다고 가정할 때, 밑과 같이 나올 것이다.

f(6)보다 더 많겠지만, 적을 필요가 없었다. 왜냐하면 f(7)이상의 답은 전부 X일 것익 때문이다. 만약 MID= 5 라면 5이상의 값들은 더 이상 안 봐도 된다. 왜냐하면, d = 5 인데도, 매듭 사이 거리를 충족 못하는데, 5를 초과한 값들에 대해서도 당연히 f(d) = false라는 게 예측 가능하기 때문이다.

3️⃣ `YES or NO` 답의 범주 내에서 이분 탐색으로 답 찾기

이미 2️⃣에서 다루었지만, 구한 일련의 f(d) Data Set에서 이분 탐색을 통해 원하는 답을 찾으면 된다. Thread Knots 문제에서는 f(d) = true인 값 중 제일 오른쪽에 있는 값이 답이 될 것이다.

그러면 f(d) 결과 DATA SET을 모조리 구해야 하나요? 🤔

아니다. 위에서 설명했다시피, f(d)의 결과는 예측 가능하다. 따라서 mid에 해당하는 값만 그때 그때 구하며 문제를 풀어가면 된다.

저작자표시