Quantization(양자화)

문제

Quantization(양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 1000 이하의 자연수들로 구성된 수열을 s가지의 자연수만을 사용하도록 양자화하려고 한다. 1 2 3 4 5 6 7 8 9 10을 두 가지 숫자만을 써서 표현하려면 3 3 3 3 3 7 7 7 7 7 또는 1 1 1 1 1 10 10 10 10 10처럼 표현할 수 있다. 이중 각 숫자별 오차 제곱의 합의 최소치를 구하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(1~50)이 주어짐.

각 테스트 케이스의 첫 줄에는 수열의 길이 n(1~100), 사용할 숫자의 수 s(1~10)가 주어진다.

그 다음 줄에 n개의 정수로 수열의 숫자들이 주어지며, 수열의 모든 수는 1000 이하의 자연수이다.

예제 입력 및 출력

입력

2

10 3

3 3 3 1 2 3 2 2 2 1

9 3

1 744 755 4 897 902 890 6 777

 

출력

0

651

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int Case;
// cache[pivot][length] = pivot에서 길이 length만큼 부분수열의 오차제곱 최솟값을 저장
int cache[100][100]; 

class Quantization {
private:
	int arrlength; //수열의 길이
	int usenum; // 사용할 숫자의 수
	vector<int> sequence; //수열
public:
	void setQuant() {
		int tmp;
		cin >> arrlength >> usenum;
		for (int i = 0; i < arrlength; i++) {
			cin >> tmp;
			sequence.push_back(tmp);
		}
	}
	//버블정렬
	void bubblesort() {
		for (int i = 1; i < arrlength; i++) {
			for (int j = 0; j < arrlength - i; j++) {
				if (sequence[j] > sequence[j + 1])
					swap(sequence[j], sequence[j + 1]);
			}
		}
	}
	//오차제곱 최솟값을 찾는 함수
	int findMinError(int pivot, int length, int part) {
		int average = 0;
		int sum = 0;

		//main함수에서 처음 호출할때 피벗이 -1이므로 예외처리
		if (pivot >= 0) {

			//기저사례- 현위치에서 해당길이만큼 수열의 오차제곱합이 이미 계산된경우 바로 반환
			if (cache[pivot][length] != -1)
				return cache[pivot][length];

			//부분수열의 총합
			sum = sequence.at(pivot);
			for (int i = 1; i < length; i++)
				sum += sequence.at(pivot + i);
			average = round(sum / (double)length); //평균값(반올림한 값)
			//부분수열의 오차제곱합
			sum = 0;
			for (int i = 0; i < length; i++) {
				sum += (sequence.at(pivot + i) - average) * (sequence.at(pivot + i) - average);
			}
			cache[pivot][length] = sum;
		}

		//마지막 부분수열일경우 바로 반환
		if (part == usenum)
			return cache[pivot][length];

		//마지막 부분수열이 아닐경우 현재 pivot을 기준으로 가능한 모든 길이의 부분수열을 만든다
		for (int i = 1; i <= arrlength - pivot - length - usenum + part + 1; i++) {
			//다음번 부분수열이 마지막 부분수열일경우 길이는 항상 동일
			if (part + 1 == usenum) {
				cache[pivot][length] = sum + findMinError(pivot + length, arrlength - pivot - length, part + 1);
				break;
			}
			//다음번 부분수열이 마지막이 아니라면 길이는 달라짐 -길이별 최소값을 찾는다
			else {
				if (i == 1)
					cache[pivot][length] = sum + findMinError(pivot + length, 1, part + 1); //길이 1일때 오차제곱 최솟값 바로 저장
				else
					//길이 2 이상일때부터는 최솟값을 cache에 저장
					cache[pivot][length] = min(cache[pivot][length], sum + findMinError(pivot + length, i, part + 1)); 
			}
		}
		//결과 최솟값 반환
		return cache[pivot][length];
	}
};

Quantization* quant;

int main(void) {
	cin >> Case;

	quant = new Quantization[Case];

	for (int i = 0; i < Case; i++)
		quant[i].setQuant();

	for (int i = 0; i < Case; i++) {
		memset(cache, -1, sizeof(cache));
		quant[i].bubblesort(); //입력받은 수열을 정렬
		cout << quant[i].findMinError(-1, 1, 0) << endl; //오차 최솟값 구하는 함수 호출
	}
}

문제풀이

1. cache값 설정

   - cache[pivot][length]: 수열의 pivot번째 수에서 길이가 length인 부분 수열의 오차 제곱 값을 저장

 

2. 기저사례

   - cache값이 이미 계산되었다면 부분 수열을 나눌 필요 없이 바로 반환.

 

3. 함수 탈출 조건

   - 사용할 숫자 usenum이 주어지면 총 usenum개의 부분수열을 생성해야 한다.

   - part값을 인자로 전달하여 part==usenum이 되면 마지막 부분 수열로 더 이상 부분 수열을 나눌 필요 없이 오차 제곱 값을 계산하여       바로 반환한다.

 

4. 점화식

   - 현재 부분 수열이 마지막 부분수열이 아니라면 다음번 부분 수열의 길이가 1~ (남은수열 길이-남은사용할 문자)만큼 생성할 수 있다.

   - 각각의 재귀 함수를 호출하여 반환 값 중 최솟값을 현재 cache값에 저장하여 반환한다.