양자화 (난이도: 중)

 1. 문제 설명

(1) 양자화(Quantization) 과정은 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써

자료를 손실 압축하는 과정을 말한다.

 

(2) 예를 들면, 16비트 JPG 파일을 4컬러 GIF 파일로 변환하는 것은 RGB 색 공간의 색들을 4컬러 중의 하나로

양자화하는 것이며, 키가 161, 164, 178, 184인 학생 넷을 (160대 두명, 170대 하나, 180대 하나) 라고 축약해

표현하는 것 또한 양자화라고 할 수 있다.

 

(3) 여기서는 1,000 이하의 자연수들로 구성된 수열을 S가지의 자연수만을 사용하도록 양자화하려고 한다.

 

(4) 예를 들어, 수열 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으로 할 수도 있다.

 

(5) 이때 이 중 각 숫자별 오차 제곱의 합을 가능한 한 최소화하는 양자화 결과를 찾아내는 프로그램을 작성하시오.

( 예를 들면, 1 2 3 4 5를 2 2 3 3 3으로 양자화하면 각 숫자별 오차는 -1, 0, 0, 1, 2이고, 오차 제곱의 합은 1+0+0+1+4=6

이 된다. )

( 그러나 2 2 2 4 4로 양자화하면 오차 제곱의 합은 1+0+1+0+1=3이 된다. 그러므로 2 2 2 4 4가 더 최소치가 되므로

정답은 2 2 2 4 4가 된다. )

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 입력의 첫 줄에는 테스트 케이스의 수 C(1<=C<=50)

(2) 그 후 두 번째 줄에 수열의 길이 N(1<=N<=100), 사용할 숫자의 수 PARTS(1<=PARTS<=10)

(3) 그 후 세 번째 줄에 수열 A(A<=1000)

 

출력 조건

(1) 주어진 수열을 S개의 수로 양자화할 때 오차 제곱의 합의 최소치를 출력

 

입력 예제

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

 

 

 

 

3. 제약 조건

(1) 프로그램은 2초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야 한다.

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1) 모든 숫자를 다 양자화 했을 경우

(2) 숫자는 남아있는데 더 묶을 수 없는 경우

 

 

 

 

6. 코드 및 풀이

이 문제를 재귀적으로 해결할 경우 아래의 사진의 함수처럼 지금까지 사용한 숫자들을 알리는 것이 필요하다.

* U가 지금까지 한 번 이상 사용한 숫자들의 집할일 때 A에 속한 수를 양자화해서 얻을 수 있는 최소 오차 제곱의 합

 

 

그러나 이런 완전 탐색 코드는 실로 엄청나게 많은 수의 답을 하나하나 만들게 된다.

* 예를 들어, 수열 A가 1000이하의 자연수로 구성되며 U의 크기가 10인 경우에만도 (1000)C(10)의 부분문제 발생

 

 

이럴 경우 답의 형태를 제한함으로써 쉽게 문제를 접근할 수 있다.

 

예제 입력을 포함한 작은 입력 몇 개를 손으로 풀어 보면, 두 숫자 a<b에 대해 a에 대응되는 숫자가 b에 대응되는

숫자보다 커서는 안 된다는 사실이 존재한다.

* 예를 들어, 1을 7로 바꿨는데 9를 6으로 바꾸는 것은 절대로 최적해가 될 수 없다는 것을 알 수 있다.

 

 

그러므로 이것을 일반화하면 주어진 수열을 정렬하면 같은 숫자로 양자화되는 숫자들은 항상 인접해 있다는 것을

알 수 있다.

* 예를 들어, {1, 2, 3, 4}를 양자화하는데, 최적해가 {2, 2, 3, 2}와 같은 형태일리는 없다.

 

 

방법은 입력에 주어지는 수들을 정렬한 뒤, 인접한 숫자끼리 묶음으로 적절히 분할하고 각 묶음을 한 숫자로

표현하여 오류를 최소화한다.

* 예를 들어, {1, 4, 6, 744 755, 777, 890, 897, 902} -> {1, 4, 6}, {744, 755, 777}, {890, 897, 902}로 분할 후

각각 4, 759, 896으로 표현

 

따라서 이 문제는 주어진 수열을 S개의 묶음으로 나누는 문제가 된다.

 

 

먼저 아래의 7. 점화식을 이해한 뒤 아래의 코드를 보는 것이 좋다.

 

 

 

public class QUANTIZE {
	private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	
	// 각각 수열 A의 크기와 사용할 숫자의 수(1~10)
	private static int N, PARTS;
	
	// 양자화해야 할 수열
	private static int[] A;
	
	// A[]의 부분합을 저장한다.
	// ex) pSum[i] = A[0] + ... + A[i]
	private static int[] pSum;
	
	// A[]의 제곱의 부분합을 저장한다.
	// ex) pSqSum[i] = A[0]^2 + ... + A[i]^2
	private static int[] pSqSum;
	
	private static int[][] cache;
	
	public static void main(String[] args) throws IOException {
		StringTokenizer st;
		int C = Integer.parseInt(sc.readLine());
		
		for(int i=0; i<C; i++) {
			st = new StringTokenizer(sc.readLine());
			N = Integer.parseInt(st.nextToken());
			PARTS = Integer.parseInt(st.nextToken());
			
			A = new int[N];
			pSum = new int[N];
			pSqSum = new int[N];
			cache = new int[101][101];
			
			st = new StringTokenizer(sc.readLine());
			for(int y=0; y<N; y++) {
				A[y] = Integer.parseInt(st.nextToken());
			}
			preCalc();
			sb.append(solve(0, PARTS)+"\n");
		}
		System.out.println(sb);
	}
	
	private static int solve(int from, int parts) {
		// 기저 사례(1): 모든 숫자를 다 양자화 했을 때
		if(from==N) return 0;
		
		// 기저 사례(2): 숫자는 아직 남았는데 더 묶을 수 없을 때 아주 큰 값을 반환
		if(parts==0) return 9999999;
		
		if(cache[from][parts] != 0) return cache[from][parts];
		
		int ret = 9999999;
		
		// 조각의 길이를 변화시켜 가며 최소치를 찾는다.
		for(int partSize=1; from+partSize<=N; partSize++) {
			cache[from][parts] = ret = Math.min(ret, minError(from, from+partSize-1)+solve(from+partSize, parts-1));
		}
		return ret;
	}
	
	// 오차 제곱의 합을 반환하는 메서드
	private static int minError(int lo, int hi) {
		int sum = pSum[hi] - (lo==0 ? 0:pSum[lo-1]);
		int sqSum = pSqSum[hi] - (lo==0 ? 0:pSqSum[lo-1]);
		
		int m = Math.round((float)sum / (hi - lo +1));
		return m*m* (hi-lo+1)- 2*m*(sum) + sqSum;
	}
	
	// 정렬, 수열 A에 대한 합, 제곱의 합을 구하는 메서드
	private static void preCalc() {
		Arrays.sort(A);
		pSum[0] = A[0];
		pSqSum[0] = A[0]*A[0];
		for(int i=1; i<N; i++) {
			pSum[i] = pSum[i-1] + A[i];
			pSqSum[i] = pSqSum[i-1]+A[i]*A[i];
		}
	}
}

 

 

 

 

 

7. 점화식

 

- minError()는 아래와 같이 세 가지 일을 한다.

(1) 주어진 구간을 어떤 수로 표현해야 할지 결정

(2) 결정한 수 m(고른 숫자들의 평균)으로 해당 구간을 표현했을 때 오차를 계산

(3) 오차 제곱의 합을 계산하여 리턴

 

 

- 이때, 오차 제곱의 합은 보편적으로 사용되는 아래의 그림의 공식을 이용한다.

오차 제곱의 합

 

- 이때 미분을 이용하면 길이 2 이상인 구간 수열[a...b]에 대해 오차 제곱의 합을 최소화 하는 m을 찾을 수 있다.

 

- 위의 식(오차 제곱의 합)은  m에 대한 2차식이고, 2차항의 계수가 양수이므로 아래의 그림처럼 미분을 통해 최소점을

찾을 수 있다.

 

 

 

- 또한 오차 제곱의 합에 필요한 수열 A[a...b]대한 합이 아래의 그림처럼 미리 구할 필요가 있다.

( 코드에서는 pSum[]과 pSqSum[]을 구현할 것이다. )

 

 

- 추가적으로 만약 두 숫자 a<b에 대해서 a에 대응되는 숫자가 b에 대응되는 숫자보다 커서는 안되는 사실이 있다.

그러므로, 정렬 또한 미리 계산해야 한다. 

* preCalc()에 정의한다.