처음 이분 탐색 문제를 접했을 때, 이분 탐색? 그거 쉬운거 아니야? 하고 덤볐다가 크게 데여서 정리하게 되었다.
원리를 모르고 접근하면 창의적인 오답을 남발하게 되는 장르인 것 같다.
블로그는 https://sarah950716.tistory.com/16 를 참고하였다.
2613번은 골드2 문제로, 파라메틱 서치 입문 문제로는 적절하지 않으니 2805 나무 자르기(실버2)를 먼저 풀어보는 것을 추천한다.
파라메틱 서치란
파라메트릭 서치는 이진탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘이다.
이를 최적화 문제를 결정 문제로 바꾸는 것이라고 표현할 수 있다.
최적화 문제를 파라메틱 서치로 풀 수 있는 조건은 다음과 같다.
1. 정답이 될 수 있는 값인지 아닌지를 쉽게 판단할 수 있어야한다.
2) (최솟값을 구하는 경우) 최솟값이 x라면, x이상의 값에 대해서는 모두 조건을 만족
3) (최댓값을 구하는 경우) 최댓값이 x라면, x이하의 값에 대해서는 모두 조건을 만족또 조건을 만족하는 범위가 연속적이어야 한다.
파라메틱 서치는 조건을 만족하는 연속하는 범위내에서 최대 혹은 최소를 찾아내는 문제이다.
그런데 조건을 만족하는 범위가 연속적이지 않다면 반례가 생길 수 있다.
백준 2613
파라메틱 서치 예제로 백준 2613을 풀어보았다.
이 문제는 문제풀이도 풀이인데, 답을 출력하는 과정이 많이 번거로웠다.
답을 출력하는 코드는 본 포스팅 주제와는 무관하니 설명을 생략한다.
문제 포스팅은 아니니 문제요약은 하지 않겠다.
백준 2613번 숫자구술
이 문제를 살펴보면 최적화 문제임을 알 수 있다.
각 그룹의 합 중 최댓값이 최소가 되도록 M개의 그룹으로 나누는 것이기 때문이다.
Z: min(max(그룹의 합)) 이라고 할 수 있겠다.
그러면 이 최적화 문제를 파라메틱 서치로 해결할 수 있는지를 알아야 한다.
정답이 될 수 있는 값인지 아닌지를 쉽게 판단할 수 있는가?
사실 이것이 가장 중요한 조건이고 아래 두 조건은 적절성 여부만 확인한다고 볼 수 있다.
이 조건이 맞는지 판단하면, 풀이도 거의 완성되기 때문이다.
나는 이 조건에서 한 가지를 더 추가하고 싶다.
바로 "어떤 기준으로 인덱싱할지 명확한가?" 이다.
파라메틱 서치는 기본적으로 바이너리 서치가 응용되는 방법인데, 바이너리 서치처럼 찾고자하는 값이 현재 값보다 크다면 start를 mid + 1로 바꾸고 작다면 end를 mid - 1로 바꾸는 것처럼, 우리의 결정문제도 이와 같이 명확한 기준으로 인덱스를 바꿀 수 있어야한다.
먼저 문제에 나와있는 예제를 살펴보겠다.
어떤 값이 정답인지를 직관적으로 확인해보자.
다음과 같은 구슬이 있다고 했을 때,
아래처럼 그룹을 형성할 수 있다.
이 경우 17보다 최댓값이 작을 수 없으므로 17이 정답이다.
그렇다면 두가지 의문을 해결해야한다.
두 가지 의문을 쉽게 해결할 수 있다면 우리는 파라메틱 서치를 적절히 이용할 수 있을 것이다.
1. 그룹이 3개인 것을 어떻게 알았는가?
그림2와 3에서 사람은 육안으로 보고 바로 그룹의 개수를 확인할 수 있지만, 우리가 이것을 코드로 쉽게, 즉 낮은 복잡도로 작성할 수 있어야 파라메틱 서치를 적용할 수 있다.
먼저 최대값을 안다고 가정하겠다.
현재 그룹의 최대값이 17이라고 했을 때, 그룹의 개수를 알 수 있는 방법은 순차적으로 구술의 수를 더하다가 처음으로 17을 넘겼을 때 그룹의 개수가 늘어난다는 사실을 이용하는 것이다.
다음 그림처럼 맨 처음 구슬에서 시작해서 처음 17을 넘기는 것은 5번째 구슬을 더했을 때이다.
따라서 1번째 구슬부터 4번째 구슬이 한 그룹임을 알 수 있다.
같은 방법으로 다음 그룹도 알 수 있다.
5번째 구슬에서 시작해서 처음으로 17을 넘기는 것은 7번째 구슬이 더해졌을 때이다.
따라서 5, 6번 구슬이 하나의 그룹을 이룬다.
이런 방식으로 우리는 그룹이 총 3개라는 것을 알 수 있다.
즉, 우리는 O(n)의 복잡도로 그룹의 개수를 알 수 있다.
2. 최솟값(최적값)을 어떻게 구할 것인가?
위의 방법으로 그룹을 구하는데 최대값이 10이라고 가정해보자.
그러면 아래 그림과 같이 그룹이 형성이 된다.
이를 보고 우리는 최댓값이 구하고자 하는 최적치보다 작으면 더 많은 그룹이 형성된다는 것을 알 수 있다. (극단값으로 16을 최대치로 설정해보면 5개의 그룹이 형성된다.)
그러면 17보다 큰 값인 21로 최대값을 설정해보자
그러면 아래 그림과 같이 그룹이 형성된다.
그런데 이 그림을 보면 알 수 있듯이 17보다 큰 값이라고 해서 3개보다 적은 그룹이 만들어지지는 않는다. (물론 17보다 훨씬 큰 값은 17보다 더 적은 개수의 그룹이 만들어진다. ex. 44)
그러면 이렇게 생각해 볼 수 있다.
3개의 그룹을 만드는 수 중에서 가장 작은 값을 출력하면 그것이 답이다.
이 두 가지 의문을 해결했으니 우리는 쉬운 방법으로 정답인지 아닌지를 판단할 수 있게 됐다.
또한 그룹의 개수를 기준으로 그룹이 많다면 최적값이 현재 값보다 더 크다는 것을, 그룹이 같거나 적다면 현재 값보다 더 작음을 알게 되었다.
따라서 우리는 명확한 기준으로 인덱싱 또한 할 수 있게 되었다.
이제 코드로 구현하는 일만 남았다.
2. 조건을 만족하는 범위가 연속적인가?
3. max(그룹의 합)의 최솟값이 x라면, x이상의 값에 대해서는 모두 조건을 만족하는가?
이 두가지는 조금만 고민해보면 알 수 있으니 설명을 생략하겠다.
코드:
풀이 코드보다 print_answer 코드가 너무 길어졌다.
print_answer 함수를 간략하게 짤 방법을 고민해보아야겠다.
#include <iostream>
#include <algorithm>
#define MAX 300
using namespace std;
int n, m;
void print_answer(int *arr, int start, int m);
int main()
{
int sum, count, start, end, mid, idx;
int arr[MAX] = {0};
start = 0;
end = 0;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
if (start < arr[i])
start = arr[i];
end += arr[i];
}
while (start <= end)
{
sum = 0;
idx = 0;
count = 1;
mid = (start + end) / 2;
for (int i = 0; i < n - 1; i++)
{
sum += arr[i];
if (sum + arr[i + 1] > mid)
{
sum = 0;
count++;
}
}
if (count > m)
start = mid + 1;
else
end = mid - 1;
}
print_answer(arr, start, m);
}
# 정답을 출력하는 함수
void print_answer(int *arr, int start, int m)
{
int sum, count, idx, balancer, tem, group[MAX] = {0};
cout << start << endl;
sum = 0;
count = 1;
idx = 0;
for (int i = 0; i < n - 1; i++)
{
sum += arr[i];
if (sum + arr[i + 1] > start)
{
group[idx] = count;
idx++;
sum = 0;
count = 1;
}
else
count++;
}
group[idx] = count;
count = 0;
for (int i = 0; i < m; i++)
{
if (group[i] != 0)
count++;
idx++;
}
balancer = m - count;
for (int i = 0; i < m; i++)
{
if (group[i] > 1 && balancer > 0)
{
for (int j = 0; j < min(balancer, group[i] - 1); j++)
cout << 1 << " ";
tem = group[i] - 1;
group[i] = max(1, group[i] - balancer);
balancer -= tem;
cout << group[i] << " ";
}
else
if (group[i] != 0)
cout << group[i] << " ";
}
}
