이번 포스트에서는 듣기에도 생소한 Parametric Search를 배워볼 것이다.
이게 뭔가 싶어서,, 일단 ChatGPT에 던져봤다.
그랬더니 아예 개념과 예시 문제까지(!) 다 줘버려서 이걸 토대로 큰 그림부터 그려보려고 한다.
Parametric Search?
Parametric Search란 최적화 문제를 해결하는 데 사용되는 알고리즘 기법이다. 주로 함수의 최적값(최대/최소)를 도출하는 특정 값을 탐색하는데 사용된다.
말이 좀 어려운데 그냥 주어진 조건을 만족하면서 결과가 최적인 매개 변수를 찾아 나가는 알고리즘을 설명하는 것 같다. 근데 이건 대부분의 알고리즘 문제가 그렇지 않나,,?
최적화 문제? 결정 문제?
Parametric search에 대해 이것저것 찾다보니 '최적화 문제를 결정 문제로 바꿔 푸는 알고리즘'이라는 식의 설명을 자주 보게 되는 것 같다. 최적화 문제와 결정 문제 각각의 정의를 좀 확실히 알고 넘어가자.
최적화 문제 (Wikipedia)
수학, 컴퓨터 과학 및 경제학에서 최적화 문제는 가능한 모든 솔루션 중에서 최상의 솔루션을 찾는 문제이다. 최적화 문제는 변수가 연속적인지 불연속적인지에 따라 두 가지 범주로 나눌 수 있다.
- 불연속 변수를 사용하는 최적화 문제를 이산 최적화라고 하며 정수, 순열 또는 그래프와 같은 개체를 셀 수 있는 집합에서 찾아야 한다.
- 연속 변수가 있는 문제를 연속 최적화 문제라 하며, 연속 함수에서 최적 값을 찾아야 한다.
아무래도 자료 구조를 활용한 알고리즘 문제 해결을 주로 하다보니 이산 최적화에 초점을 맞추면 될 것 같다. 셀 수 있는, 이산적인 어떤 입력이 주어질 때 주어진 조건을 만족하는 최상의 솔루션을 찾는 문제를 최적화 문제로 정의할 수 있을 것 같다.
결정 문제 (Wikipedia)
계산 이론에서 결정 문제란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다. 예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 하는 질문이 있다. 답은 x와 y 값에 따라 '예' 또는 '아니오' 중 하나가 될 수 있다. 일반적으로 계산 가능한 문제의 해집합은 열거 가능한 해집합의 유한한 부분 집합이기 때문에, 모든 문제는 결정 문제로 환원될 수 있다.
딱 두 부분이 눈에 들어오는데 이를 바탕으로 오늘 해결할 Parametric Search, '최적화 문제를 결정 문제로 바꿔 푸는 알고리즘'을 풀어 설명하면 '이산적인 입력이 들어왔을 때 최적값을 구하는 문제를 예-아니오 답이 있는 질문으로 바꿔 푸는 알고리즘' 정도인 것 같다.
이분 탐색과 Parametric Search
풀어 쓰긴 했지만 좀 막연하다. Python for CodingTest (feat.ChatGPT)에 의하면, Parametric Search는 아래 두 단계로 진행된다고 한다.
- 결정 문제로 변환 : 원래의 문제를 결정 문제로 바꿉니다. 예를 들어, "어떤 값 x 이하의 최대 값을 찾는 문제"를 "특정 값 x를 만족하는가" 라는 결정 문제로 바꿀 수 있습니다.
- 이분 탐색 적용 : 변환된 결정 문제에 이분 탐색을 적용합니다. 예를 들어, 가능한 모든 값 x에 대해 이분 탐색을 수행하며, 각 단계에서 해당 값 x가 문제의 조건을 만족하는지 확인합니다. 이분 탐색을 통해 최적의 답을 찾아내는 것이 가능해집니다.
음 뭐랄까, 최적해를 구해야 하는 문제에서 '최적해에 도달했는가?'라는 질문을 이분 탐색해가며 최적해를 만드는 입력 값의 범위를 좁혀 나가도록 하는 방법론 정도 될 것 같다.
CDD
ChatGPT-Driven-Development. 과연 챗선생께서 주신 문제는 Parametric Search 문제인지, 해결 방법은 옳게 되었는지 고민해보자.
깡!
이거 백준에 있는 문제였다! 디게 유명한 문제인가보다 어쩐지 낯이 익더라.
문제는 백준 2805번 S2 난이도 '나무 자르기'이다.
접근 : 이분 탐색
딱 보면 알겠지만 나무의 수가 무지막지하게 많기 때문에 무식하게 가장 큰 나무의 높이부터 하나씩 내려가면서 찾으면 시간 초과가 날 것이다. 그럼 뭐다? 톱의 높이를 이분 탐색해서 찾는다!
톱의 높이를 이분 탐색해서 찾기로 했으니 상한(high)과 하한(low)을 정해야 한다.
하한은 뭐, 톱이 땅으로 꺼질 수는 없으니 0으로 하고(높이가 0인 이상한 나무 빼고는 다 벨 수 있다),
상한은,, 굳이 가장 높은 나무보다 높은 위치까지 고려해줄 필요가 없으므로 가장 높은 나무의 높이로 할 수 있겠다(모든 나무를 통째로 벨 수 있다).
문제에서 주어진 예제, 총 7 이상의 목재가 필요할 때 나무의 높이가 각각 {20, 15, 10, 17}인 상황을 생각해보자.
- 이분 탐색을 수행하려면 나무의 높이를 정렬해야 한다.
{10, 15, 17, 20} - 이제 이분 탐색을 시작할 건데,
[low, high] = [0, max(heightsOf)] = [0, 20]으로 한다. [low, high] = [0, 20],mid = (0+20) / 2 = 10
3-1. 가장 작은 나무부터 순서대로, 톱의 높이가 10일 때 목재를 얻을 수 있는 톱의 높이를 찾는다.
3-2. 2번째 15부터 차례로{5, 7, 10}, 총 22만큼의 목재를 얻을 수 있다. (최고 높이 갱신)
3-3. 필요한 목재는 7이므로, 톱의 높이를 높여 나무를 덜 자르자. ([0, 20] => [10, 20])[low, high] = [10, 20],mid = (10+20) / 2 = 15
4-1. 가장 작은 나무부터 순서대로, 톱의 높이가 15일 때 목재를 얻을 수 있는 톱의 높이를 찾는다.
4-2. 3번째 17부터 차례로{2, 5}, 총 7만큼의 목재를 얻을 수 있다. (최고 높이 갱신)
4-3. 필요한 목재는 7이므로, 필요한 만큼 목재를 얻었지만 톱을 더 높게 올릴 수 있을지도 모르므로 톱을 더 높게 올려보자. ([10, 20] => [15, 20])[low, high] = [15, 20],mid = (15+20) / 2 = 17
4-1. 가장 작은 나무부터 순서대로, 톱의 높이가 17일 때 목재를 얻을 수 있는 톱의 높이를 찾는다.
4-2. 4번째 20만 잘리므로, 총 20-17=3만큼의 목재를 얻을 수 있다.
4-3. 필요한 목재는 7이므로, 톱을 너무 내려서 목재가 부족하니 톱을 내리자. ([15, 20] => [15, 17])[low, high] = [15, 17],mid = (15+17) / 2 = 16
4-1. 가장 작은 나무부터 순서대로, 톱의 높이가 16일 때 목재를 얻을 수 있는 톱의 높이를 찾는다.
4-2. 3번째 17부터 차례로{1, 4}, 총 5만큼의 목재를 얻을 수 있다.
4-3. 필요한 목재는 7이므로, 톱을 너무 내려서 목재가 부족하니 톱을 내리자. ([15, 17] => [15, 16])[low, high] = [15, 16],mid = (15+16) / 2 = 15
4-1. 가장 작은 나무부터 순서대로, 톱의 높이가 15일 때 목재를 얻을 수 있는 톱의 높이를 찾는다.
4-2. 2번째 15부터 차례로{5, 7, 10}, 총 22만큼의 목재를 얻을 수 있다.
4-3. 필요한 목재는 7이므로, 필요한 만큼 목재를 얻었지만 톱을 더 높게 올릴 수 있을지도 모르므로 톱을 더 높게 올려보자. ([15, 16] => [15, 15])- 앗! 이분 탐색이 더 불가능하다! (
15 == 15) 이제 갱신된 톱의 최고 높이인 15를 반환한다.
구현 1 : 이분 탐색
위 과정을 코드로 표현하면 아래와 같다.
public static void main(String[] args) throws Exception {
st = new StringTokenizer(in.readLine());
// 나무의 개수
final int NUM_OF_TREES = Integer.parseInt(st.nextToken());
// 필요한 최소 목재 길이
final int REQUIRED_WOODS = Integer.parseInt(st.nextToken());
// 나무의 높이
int[] heightOf = new int[NUM_OF_TREES];
st = new StringTokenizer(in.readLine());
for (int tree = 0; tree < NUM_OF_TREES; tree++) {
heightOf[tree] = Integer.parseInt(st.nextToken());
}
// 이분 탐색을 위한 정렬
Arrays.sort(heightOf);
// 최적해 = 가능한 가장 높은 톱의 높이
long resultSawHeight = Long.MIN_VALUE;
// 이분 탐색을 위한 톱 높이의 가능한 구간
int minSawHeight = 0;
int maxSawHeight = heightOf[NUM_OF_TREES - 1];
// 이분 탐색이 가능할 때까지 갱신한다.
while (minSawHeight < maxSawHeight) {
// 톱의 높이를 선택해서
int candidateSawHeight = (minSawHeight + maxSawHeight) >> 1;
// 나무를 자를 수 있다면 목재 양을 누적한다.
long woods = 0;
for (int tree = 0; tree < NUM_OF_TREES; tree++) {
woods += Math.max(heightOf[tree] - candidateSawHeight, 0);
}
// 필요한 목재 이상 얻었다면
if (woods >= REQUIRED_WOODS) {
// 톱의 높이를 갱신해주고
resultSawHeight = candidateSawHeight;
// 최적해를 얻을 수도 있으므로 더 높은 톱 높이를 탐색
minSawHeight = candidateSawHeight + 1;
}
// 그렇지 못했다면
else {
// 더 잘라야 하므로 낮은 톱 높이를 탐색
maxSawHeight = candidateSawHeight;
}
}
System.out.println(resultSawHeight);
}
뭔가 장황한데 그냥 적당한 톱의 높이를 선형 탐색이 아닌 이분 탐색으로 찾는 것뿐이다.
이렇게 풀어도 답은 나온다! 하지만 가장 작은 나무부터 순서대로가 좀 걸리적거리지 않는가?!
여담으로 문제 다 풀어놓고 얻을 수 있는 목재의 총 길이를 누적하는데 int를 써서 오류가 났었다. 항상 입력값의 범위를 잘 보자 잘,,,,,,
구현 2 : 자를 수 있는 나무 이분 탐색으로 구하기
자를 수 있는 가장 작은 나무를 구할 때도 이분 탐색을 쓸 수 있지 않을까?
정확히는 저번 포스트에서 배운 lower bound를 써주면 된다.
lower bound는 일정 구간 안에서 찾으려는 값 이상인 가장 첫 위치
이니까, 정렬된 나무 높이 배열에 대해서 톱의 높이(찾으려는 값)로 lower bound를 구한다는 것은 곧 자를 수 있는 나무들 중 가장 낮은 나무의 위치를 찾는 것과 같다고 할 수 있겠다.
Lower bound를 써서 성능을 개선해보자.
public static void main(String[] args) throws Exception {
st = new StringTokenizer(in.readLine());
// 나무의 개수
final int NUM_OF_TREES = Integer.parseInt(st.nextToken());
// 필요한 최소 목재 길이
final int REQUIRED_WOODS = Integer.parseInt(st.nextToken());
// 나무의 높이
int[] heightOf = new int[NUM_OF_TREES];
st = new StringTokenizer(in.readLine());
for (int tree = 0; tree < NUM_OF_TREES; tree++) {
heightOf[tree] = Integer.parseInt(st.nextToken());
}
// 이분 탐색을 위한 정렬
Arrays.sort(heightOf);
// 최적해 = 가능한 가장 높은 톱의 높이
long resultSawHeight = Long.MIN_VALUE;
// 이분 탐색을 위한 톱 높이의 가능한 구간
int minSawHeight = 0;
int maxSawHeight = heightOf[NUM_OF_TREES - 1];
// 이분 탐색이 가능할 때까지 갱신한다.
while (minSawHeight < maxSawHeight) {
// 톱의 높이를 선택해서
int candidateSawHeight = (minSawHeight + maxSawHeight) >> 1;
// 나무를 자를 수 있다면 목재 양을 누적한다.
long woods = 0;
// 주목!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
for (int tree = getLowerBound(heightOf, candidateSawHeight + 1); tree < NUM_OF_TREES; tree++) {
woods += heightOf[tree] - candidateSawHeight;
}
// 필요한 목재 이상 얻었다면
if (woods >= REQUIRED_WOODS) {
// 톱의 높이를 갱신해주고
resultSawHeight = candidateSawHeight;
// 최적해를 얻을 수도 있으므로 더 높은 톱 높이를 탐색
minSawHeight = candidateSawHeight + 1;
}
// 그렇지 못했다면
else {
// 더 잘라야 하므로 낮은 톱 높이를 탐색
maxSawHeight = candidateSawHeight;
}
}
System.out.println(resultSawHeight);
}
public static int getLowerBound(int[] numbers, int targetNum) {
int low = 0;
int high = numbers.length;
while (low != high) {
int mid = (low + high) >> 1;
if (numbers[mid] >= targetNum) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}사실 다른건 다 같은데, 잘라서 목재를 얻을 수 있는 첫 나무를 얻는데 lower bound를 활용하는 부분만 다르다. 또 이전까지 Math.max 함수를 사용해서 얻을 수 있는 목재의 양이 음수가 되지 않도록(heightOf[tree] - candidateSawHeight) 했던 코드를 뺐다. 어차피 톱의 높이와 같았거나(candidateSawHeight가 배열에 포함되어 있는 경우) 모든 나무의 높이보다 낮았거나, 높았을 것이기 때문이다(lower bound가 0, 또는 heightOf.length).
그리고 원래 getLowerBound(heightOf, candidateSawHeight)로 썼다가 두 번째 인자에 1을 더해서 getLowerBound(heightOf, candidateSawHeight+1)로 써줬는데, lower bound 특성상 candidateSawHeight와 동일한 높이의 나무가 여러 개 있으면 불필요하게 그 높이의 나무들만큼 0을 더해준다고 생각해 고쳐 썼는데 실행 시간이 유의미하게 차이 나는 것 같진 않다.
마무리
그럼 오늘의 주제, Parametric Search에 대한 정의와 엮어서 마무리 지어보자.
이산적인 입력이 들어왔을 때 최적값을 구하는 문제를 예-아니오 답이 있는 질문으로 바꿔 푸는 알고리즘
- 이산적인 입력이 들어왔을 때 : 나무의 높이로 구성된 배열은 이산적인, 셀 수 있는 입력이다.
- 최적값을 구하는 문제를 : 우리가 구하고 싶은 건 최소 정해진 양 만큼의 목재는 얻을 수 있되 나무를 최대한 적게 자를 수 있는 톱의 높이를 구하는 것이다.
- '나무를 최대한 적게' 자른다는 것은 곧 '톱의 높이를 최대한 높게'와 같다.
- 예-아니오 답이 있는 질문으로 바꿔 푸는 문제 : 문제에서 톱의 높이를 조정하는 조건 함수는 '지금 주어진 톱의 높이(매개 변수)로 원하는 최소한의 목재를 얻을 수 있는가'이고, 이 함수의 답은 '예', '아니오' 밖에 없다.
이분 탐색으로 매개 변수가 있을 수 있는 범위를 좁혀가며 최적해를 구한다, 단 주어진 명제에 대해 항상 참이 되는 매개 변수만 선택한다, 정도로 이해했는데, 다음 문제 풀어보면서 또 어떤 부분이 이렇게 구조화되는지 생각해보면 좋겠다. 빠세! 아휴 힘들다 밥 먹고 해야지 저녁은 육회비빔밥 🤪
참고 자료
- Python for CodingTest (feat.ChatGPT) : 3-03-04. Parametrict Search : 되게 깔끔하게 정리되어 있어 그대로 인용했다. 전체적으로 내용이 알차서 나중에 꼭 정독해보려고 한다!
