📝 Baekjoon 2110 문제풀이
💡문제 정의
input의 크기가 최대 200,000이므로 당연히 O(N^2)로는 풀 수 없을 것이고, O(NlogN)의 해법을 찾아야 했다. 그런데! 이전까지 풀어보았던 Binary Search 활용 문제와 닮은 듯 하면서도 다른 문제였다.
내가 지금까지 풀었던 (3-4문제밖에 안 되는 것 같지만ㅋㅋㅋ) 이분법 문제는 배열 탐색에 Binary Search를 적용해서 적절한 위치(index)를 찾는 것이었다. 그런데 이 문제는 그렇지 않다. 배열에서의 적절한 위치를 찾는 것이 아니라, 가장 인접한 두 공유기 사이의 '최대 거리'를 구해야 한다.
🚀 Parametric Search
이 문제는 단순 Binary Search가 아닌 Parametric Search를 이용해야 한다.
여기서 Parametric Search란,
- Binary Search(이진 탐색)의 응용 버전
- 특정 조건을 만족하는 최댓값, 최솟값 등을 찾는 최적화 문제에서 활용 -> 최적화 문제를 결정 문제(Yes or No, Decision Problem)으로 바꾸어 푸는 것
- mid 값이 문제의 조건을 만족하는지 안 하는지 판단 -> 만족한다면 일단 저장해두고, 범위를 좁혀서 더 탐색해 봄
개념만 봤을 때는 도무지 무슨 말인지 감도 안 잡히고 잘 이해되지 않았는데, 여러 코드를 봐보고 직접 구현을 해보니 감이 잡히는 것 같다.
// C code
// l은 현재 범위에서의 가장 왼쪽 값, r은 현재 범위에서의 가장 오른쪽 값
int l = 0, r = len - 1; // len은 배열의 길이
while (l <= r) {
int target = ~~~ // 배열에서 찾고자 하는 target 값
mid = (l + r) / 2;
if (arr[mid] == target) ~~~
else if (arr[mid] > target) r = mid - 1;
else l = mid + 1;
}일반적인 이진 탐색 코드는 위와 같이 배열 자체를 대상으로 배열의 mid값과 target 값을 비교해서 특정 연산을 수행하는 형태였다면
int min = 1; // 두 집 사이의 최소 거리
int max = arr[len - 1] - arr[0]; // 두 집 사이의 최대 거리
while (min <= max) {
~~~
}
Parametric Search를 활용하는 이 문제에서는 집의 좌표들이 저장된 원본 배열은 따로 있다. 그리고 집들 사이의 거리의 최솟값 ~ 최댓값을 대상으로 거리의 mid값을 설정하고, 해당 mid값이 문제의 조건을 만족하는지 살펴보며 연산을 수행해야 한다.
l에 대응되는 것이 min, r에 대응되는 것이 max이다.
이 블로그를 보고 도움을 많이 받았다! 이 포스트를 보면 이해가 수월할 것 같다
Binary Search와 Parametric Search의 차이점을 좀 더 간결하게 표현하자면
참고
- Binary Search: 배열에서 중앙값(middle)이 가리키는 값이 내가 찾는 값인가
- Parametric Search: 원하는 조건을 만족하는 가장 알맞는 값을 찾는 것
코드를 보고 과정을 하나하나 생각해보면 이해하기 쉽다.
1) C
# include <stdio.h>
# include <stdlib.h>
int list[200000];
int compare(const void *first, const void *second) {
return *((int *)first) - *((int *)second);
}
int main(void) {
int N, C;
scanf("%d %d", &N, &C);
for (int i = 0;i < N;i++) scanf("%d", &list[i]);
qsort(list, N, sizeof(int), compare);
int ans;
int min = 1; // 공유기 간의 최소 간격
int max = list[N - 1] - list[0]; // 공유기 간의 최대 간격
while (min <= max) {
int cnt = 1; // 일단 제일 처음에는 무조건 공유기 설치
int mid = (min + max) / 2; // 기준 간격: 이 mid를 간격으로 공유기를 설치해본다
int start = list[0]; // 시작 위치
for (int i = 1;i < N;i++) {
if (list[i] - start >= mid) { // start와 현재 위치 사이의 간격이
//mid보다 크거나 같다면
cnt++; // list[i]에 공유기 설치 가능
start = list[i]; // 시작점 다시 설정
}
}
if (cnt >= C) { // 공유기가 C보다 많이(또는 C개) 설치됨 -> 간격 넓히기
ans = mid;
min = mid + 1;
}
else { // 공유기가 C보다 적게 설치됨 -> 간격 좁히기
max = mid - 1;
}
}
printf("%d\n", ans);
return 0;
}Parametric Search(Binary Search)를 통해 적절한 간격, 다시말해 최적해를 찾는 것이다.
💡참고
