양자화 (난이도: 중)
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()에 정의한다.
