(출처) https://algospot.com/judge/problem/read/QUANTIZE
어떤 것을 기준으로 양자화를 시켜야 할까
해당 문제는 입력으로 주어진 수열을 알맞게 변환시켜 가장 최적의 답을 구해내야 한다. 이 문제를 처음 봤을 때 막막했던 점은 수열의 숫자들을 과연 어떤 것을 기준으로 변환시켜야 할지 모르겠다는 것이었다.
즉 문제를 풀기 위해서는 변환시켜야 할 숫자를 선택해야만 하는데, 수열에서 올 수 있는 숫자들은 1,000 이하의 자연수이므로 1000 이상의 수들을 고르는 것은 최적이 될 수 없다는 것까지는 쉽게 알 수 있었다. 하지만 그렇다고 1부터 1000 까지의 수를 일일이 최대 100개의 길이를 갖는 수열에 하나하나 대입해가면서 문제를 푸는 건 절대 불가능하기 때문에 변환을 시키는 특정 기준이 필요했다.
그렇다면 과연 변환시켜야 할 숫자를 어떤 것을 기준으로 골라내야 할까? 그 기준을 찾는 것을 우선해서 생각해보았다.
예제 입력과 출력을 보면서 한번 내가 직접 답을 구해보는 과정을 시뮬레이션 해봤는데,
예제 입력
9 3
1 744 755 4 897 902 890 6 777
예제 출력
651
내가 직접 답을 처음부터 따라가며 답을 구해보고자 하니까 확실히 눈에 보이는 것이 있었다. 격차가 적은 구간끼리 묶어서 변환해야 할 숫자를 골라내는 것이 가장 최적화된 답을 구할 수 있다는 것.
애시당초 예제입력부터가 눈에 쉽게 보이게끔 각 구간 별 격차를 적절하게 끊어서 주어진 느낌이라서 더욱 쉽게 알 수 있었다.
수열을 각 구간 별로 적절하게 나눌 수만 있어도 구간마다 변환에 사용할 수를 찾는 것은 상수 시간 만에 해결할 수 있으므로 결국 해당 문제는 구간을 어떻게 나눠야 하는지를 찾는 문제로 귀결되게 된다.
구간 나누기
주어질 수 있는 수열의 최대 길이는 100개, 만들 수 있는 구간의 최대 개수는 10개, 따라서 나눠질 수 있는 최대 구간의 경우의 수는 == 110 C 9 개 이다. 당연하게도 완전 탐색으로 모든 경우를 만들어가며 탐색할 수 는 없다.
따라서 메모이제이션을 통해 특정부분의 중복을 피하면서 효율적으로 구간을 나누는 방법을 생각했다.
cache[index][s] = index부터 시작해 남은 수열을 s개의 구간으로 나눠야할 때 원하는 값의 최소치 (기저사례는 s가 1일때 == 더이상 나눠야할 구간이 오로지 1개 밖에 안남았을 때)
cache[index][s] = min
(
cache[index + 1][s -1] + {index} 를 구간화한 값 ,
cache[index +2][s - 1] + {index ,index + 1} 를 구간화한 값,
, . . . ,
cache[n - s + 1][s - 1] + {index, index + 1, ... , index + n - s} 를 구간화한 값
)
해당 방법으로는 부분문제가 총 N * S 개가 만들어지고 부분문제 1개당 최대 N개에 근접하는 반복을 수행하므로 시간복잡도는 최대 O(N^2) 미만이라고 판단할 수 있다. 따라서 문제에서 주어진 입력의 범위라면 충분히 수행해 낼 수 있다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int cache[100][10];
int n, s;
vector<int> num;
int INF = numeric_limits<int>::max();
int cal(int p, int size) {
double standard = 0;
for (int i = 0; i < size; i++) {
standard += num[p + i];
}
standard = standard / size;
standard = floor(standard + 0.5);
int ret = 0;
for (int i = 0; i < size; i++) {
int temp = ((int)standard - num[p + i]);
ret += temp * temp;
}
return ret;
}
int quantize(int p, int s) {
int& ret = cache[p][s];
if (ret < INF) return ret;
if (s == 1) return ret = cal(p, num.size() - p);
for (int next = p + 1; next < n - s + 2; next++) {
ret = min(ret, cal(p, next - p) + quantize(next, s - 1));
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int testcase;
cin >> testcase;
while (testcase--) {
cin >> n >> s;
int temp;
num.clear();
for (int i = 0; i < n; i++) {
cin >> temp;
num.push_back(temp);
}
fill_n(cache[0], 1000, INF);
sort(num.begin(), num.end());
if(n <= s) {
cout << 0 << "\n";
continue;
}
int ret = quantize(0,s);
cout << ret << "\n";
}
return 0;
}기억하고 싶은 점
구간을 나누고 난 뒤에 이제 구간의 수열들을 변환시킬 특정 값을 구할때, 나는 해당 변환 값이 구간수열들의 평균 값이 될 거라고 그냥 자연스럽게 생각했다.
근데 어째서 구간수열들의 평균 값으로 변환하는 것이 오차제곱의 최소치가 될 수 있는 것인지를 명확한 이유로 설명해 보라고 묻는다면 제대로 설명을 할 자신은 없었다. 그냥 평균이 확실히 맞는 것 같은 데라는 애매모호한 느낌만이 있었을 뿐이었다.
책의 해답에서 해당 이유를 최고차항의 계수가 양수인 이차방정식의 최솟값을 미분을 이용하여 찾는 방법으로 증명하였는데 이런 명쾌한 설명을 보아하니 고등 교과 과정의 수학 내용이라도 시간 날 때 틈틈이 영상을 보면서 다시 한번 새겨놓으면 분명 도움이 될 것 같다는 생각이 들었다. 시간이 난다면 한 번씩 찾아봐야겠다.
