[알고스팟] 양자화 #Quantize, 책 8.9절

문제 

https://www.algospot.com/judge/problem/read/QUANTIZE

algospot.com :: QUANTIZE

요약하자면 주어진 수열을 s개의 숫자로 양자화 할 때, 각 숫자별 오차제곱의 합을 최소화 하는 양자화 결과를 구해야 하는 문제이다. 

 

풀이

책에 있는 풀이를 많이 참고하였다. 

먼저, a와 b라는 두개의 숫자가 있을 때 이 숫자들의 양자화 결과를 각각 A,B라고 하자. 

a<b일 때, A>B이면 안된다. (오차를 최소화 하는 것이 목표이기 때문에)

 

따라서 주어진 수열을 그대로 양자화하기 보다는 크기순으로 정렬해서 인접한 수들끼리 같은 숫자로 양자화 하는 것이 바람직하다. 

-> 정렬된 수열을 순서대로 s개의 묶음으로 분할하는 문제가 된다. 

첫 묶음의 크기가 x라면 그 다음 문제는 n-x개의 숫자들을 s-1개의 묶음으로 분할하는 문제가 된다. 

 

그리고 어떠한 묶음 p를 k로 양자화 할 때, 그 그룹내의 오차를 최소화할 수 있는 k는 p 내부의 숫자들의 평균값이 된다.

(k가 정수여야 하므로 p 내부의 숫자들의 평균값을 반올림해서 사용한다)

책에서는 이 점을 수학공식을 이용해 설명하였으나, 확률과 통계를 배운 사람이라면 이 문장을 수학공식 없이도 이해할 수 있을 것이라고 생각한다. 

 

p 내부의 평균을 구하는 작업은 O(n)의 복잡도가 소요될 수 있지만, 

0번째 수 부터 i번째 수 까지의 합을 저장하는 pSum[i]를 이용해서 O(1)로 구할 수 있다. 

a번째 ~ b번째 숫자의 평균 : ( pSum[b] - pSum[a-1] ) / b-a+1 

* a가 0일때는 a-1 인덱스를 접근할 수 없으므로 따로 처리해준다. 

 

#include <stdio.h>
#include <algorithm>
using namespace std;
//minError()를 O(1)으로 계산하기 위해 사용
int n, s;
int arr[101];
int psum[101];
int pSqSum[101]; 
const int INF = 987654321; //INT_MAX를 사용하면 안된다. 
int minError(int start,int end) { //start와 end 사이의 최소에러를 return 
	int sum,sqSum;
	if (start == 0) {
		sum = psum[end];
		sqSum = pSqSum[end];
	}
	else {
		sum = psum[end] - psum[start - 1];
		sqSum = pSqSum[end] - pSqSum[start - 1];
	}
	//start와 end사이의 수들을 평균값을 반올림한 수로 양자화
	int m = int(0.5 + (double)sum / (end - start + 1));
	//result = sum(arr[i]-m)^2
	int result = sqSum - 2 * m * sum + m * m * (end - start + 1);
	//printf("minError(%d, %d) = %d\n", start, end, result);
	return result;
}
int cache[101][11]; //주어진 수열의 start위치부터 끝 숫자 까지 parts개의 묶음으로 나타내야 할 때 가능한 가장 작은 sqError 저장 
int quantize(int start, int parts){
	if (start == n) return 0; //끝에 도달했을 때 
	if (parts == 0) return INF; //더 이상 묶을 수 없을 때, 잘못된 경우이므로 최댓값 반환
	int & ret = cache[start][parts]; 
	if (ret != -1) return ret;
	ret = INF;
	printf("ret : %d\n", ret);
	//해당 묶음의 길이를 변화시키면서 최솟값 찾기
	for (int size = 1;start + size <= n;size++) {
		ret = min(ret, minError(start, start + size - 1) + quantize(start + size, parts - 1));

	}
	return ret;
}
int main() {
	int C;
	scanf_s("%d", &C);
	for (int c = 0;c < C;c++) {
		scanf_s("%d %d", &n, &s);
		for (int i = 0;i < n;i++)
			scanf_s("%d", &arr[i]);
		sort(arr, arr+n);
		psum[0] = arr[0];
		pSqSum[0] = arr[0] * arr[0];
		for (int i = 0;i < n;i++) {
			psum[i] = psum[i - 1] + arr[i];
			pSqSum[i] = pSqSum[i - 1] + arr[i] * arr[i];
		}
		fill(&cache[0][0], &cache[101][11],-1);
		printf("%d\n", quantize(0, s));
	}
} 

minError(int start, int end) 

: start ~ end 까지가 한 묶음 일 때 (하나의 숫자로 양자화 할 때) 가능한 최소의 error return  

quantize(int start, int parts)

: start 부터의 숫자들을 parts개의 묶음으로 분리할 때 가능한 최소의 error return