[종만북]8.동적 계획법-Quantization

문제

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

Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일을 4컬러 GIF 파일로 변환하는 것은 RGB 색 공간의 색들을 4컬러 중의 하나로 양자화하는 것이고, 키가 161, 164, 170, 178 인 학생 넷을 ‘160대 둘, 170대 둘’ 이라고 축약해 표현하는 것 또한 양자화라고 할 수 있다.

1000 이하의 자연수들로 구성된 수열을 최대 S종류 의 값만을 사용하도록 양자화하고 싶다. 이 때 양자화된 숫자는 원래 수열에 없는 숫자일 수도 있다. 양자화를 하는 방법은 여러 가지가 있다. 수열 1 2 3 4 5 6 7 8 9 10 을 2개의 숫자만을 써서 표현하려면, 3 3 3 3 3 7 7 7 7 7 과 같이 할 수도 있고, 1 1 1 1 1 10 10 10 10 10 으로 할 수도 있다. 우리는 이 중, 각 숫자별 오차 제곱의 합을 최소화하는 양자화 결과를 알고 싶다.

예를 들어, 수열 1 2 3 4 5 를 1 1 3 3 3 으로 양자화하면 오차 제곱의 합은 0+1+0+1+4=6 이 되고, 2 2 2 4 4 로 양자화하면 오차 제곱의 합은 1+0+1+0+1=3 이 된다.

수열과 S 가 주어질 때, 가능한 오차 제곱의 합의 최소값을 구하는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열의 길이 N (1 <= N <= 100), 사용할 숫자의 수 S (1 <= S <= 10) 이 주어진다. 그 다음 줄에 N개의 정수로 수열의 숫자들이 주어진다. 수열의 모든 수는 1000 이하의 자연수이다.

출력

각 테스트 케이스마다, 주어진 수열을 최대 S 개의 수로 양자화할 때 오차 제곱의 합의 최소값을 출력한다.

풀이(나의 풀이)

내가 생각한 방법은 다음과 같다.

입력받은 배열을 정렬한다.
S개로 나눌 구간을 결정한다.
구간이 결정되면, 각 구간들에 대해 양자화할 숫자를 최솟값~최댓값 범위에서 찾아 저장한다.

메모이제이션을 활용할 방법에 대해 생각해본 결과, 특정 구간에 대해 오차제곱의 합이 최소화되는 값을 찾아 저장하고자 하였다. 그래서 구간들의 길이를 바꿔가며 값을 계산할 때, 앞서 계산한 값에 대한 메모이제이션을 통해 값을 불러오는 생각을 해보았다. 하지만 S개의 수로 양자화하는 구간 설정에 대해 각 구간의 범위를 재귀적으로 호출하면서 비교할지, 아니면 주어진 오름차순 배열에 대해 S개로 나눠지는 구간을 결정하는 수학식을 찾을지에 대해 생각하다 이를 해결하지 못하였다.

풀이(책 참고)

책을 참고해본 결과 내 생각과 달리, 일단 구간이 결정되면 해당 구간에 대해 양자화할 값을 찾는 것은 재귀함수 등을 사용하지 않아도 알아낼 수 있는 문제였다. 기본적으로 오차제곱합 계산 문제에서 미분을 적용하면 평균값을 통해 계산할 때 합이 최소가 되는 사실을 알 수 있다. 따라서, 메모이제이션을 적용할 부분은 아니다.

결국 구간결정에 대해 분할정복을 수행함에 있어서 메모이제이션을 활용해야 한다. 각각의 구간을 나누는 작업을 재귀적으로 수행하는데, 먼저 첫 구간의 길이를 x로 고정하면 나머지 구간 N-x에 대해 s-1개의 구간을 계산하도록 재귀함수를 설계하면 된다. 즉, 문제를 본질적으로 해결하기 위해 구간계산을 재귀함수로 찾아야 한다. 이 때의 매개변수는 (시작 위치,분할할 개수)인데, 굳이 구간의 끝부분의 인덱스를 사용하지 않아도 앞구간을 구한 뒤 나머지 구간을 재귀적으로 계산하기 때문에 시작위치만 있어도 계산이 이루어질 수 있다.

특정구간에 대한 오차제곱합을 구하기 위해선, 먼저 구간합을 구하여 평균값을 계산하고, 해당 값을 양자화값으로 한 오차제곱합을 계산하여야 한다. 이 때 주어진 구간에 대해 계산할 때 O(n)의 시간이 걸리므로 이를 더 빠르게 계산하기 위해 부분합을 통해 계산한다. pSum[i]를 0부터 i까지의 합이라고 할때, a~b구간의 부분합은 pSum[b]-pSum[a-1]을 통해 O(1)의 시간으로 계산할 수 있다(각 부분합은 사전에 초기화시킨다).

부분제곱합은 계산식을 전개하였을 때 (부분제곱합-2 X 평균 X 부분합 + 평균^2 X 개체수)로 간략화하여 계산할 수 있기 때문에 단순하게 계산할 수 있다.

이렇게 계산된 오차제곱합을 적용한다면, 재귀함수를 다음과 같이 쓸 수 있다.

// N[] : 입력받은 배열, cache[start][part] : N[start]부터 part개로 나눌때 최소의 오차제곱합
// pSum : 부분합, pSqSum : 부분제곱합
static void init() {
		Arrays.sort(N);
		pSum[0] = N[0];
		pSqSum[0] = N[0] * N[0];
		for (int i = 1; i < N.length; i++) {
			pSum[i] = pSum[i - 1] + N[i];
			pSqSum[i] = pSqSum[i - 1] + N[i] * N[i];
		}
	}

	static int quantize(int start, int parts) {
		if (start >= N.length)
			return 0;
		if (parts == 0)
			return INF;

		if (cache[start][parts] != -1)
			return cache[start][parts];

		int ret = cache[start][parts] = INF;
		for (int i = start; i < N.length; i++) {
			ret = Math.min(ret, getSSE(start, i) + quantize(i + 1, parts - 1));
		}

		cache[start][parts] = ret;
		return ret;

	}

	static int getSSE(int from, int to) {
		int sum = pSum[to] - (from == 0 ? 0 : pSum[from - 1]);
		int sqSum = pSqSum[to] - (from == 0 ? 0 : pSqSum[from - 1]);
		int min = (int) Math.round((double) sum / (double) (to - from + 1));

		int ret = sqSum - 2 * min * sum + min * min * (to - from + 1);

		return ret;
	}

start 부터의 수열에서 parts개로 양자화하여 나눈 오차제곱합의 최소를 구하는 메소드를 quantize(start,parts)라 할 때, 앞부분의 최소 오차제곱합인 getSSE(start, i)와 나머지 구간에서 parts-1개에 대한 최소 오차제곱합 quantize(i+1, parts-1)을 비교하여 최솟값을 계산할 수 있다.

지금까지 풀었던 문제들은 주어진 그대로 재귀적인 해법을 찾아 적용하였으나, 이 문제의 경우 재귀적인 해법을 적용시키기 위해 답의 형태를 제한하여(정렬 및 구간설정) 계산하여 문제를 해결하기가 까다로웠다. 또한 각 부분합과 부분제곱합을 계산하는 부분에 있어서 주어진 구간을 순회하여 푸는 방식 대신에 사전에 초기화한 부분합과 부분제곱합을 통해 특정 구간의 합을 빠르게 계산하는 부분이 인상깊었다.

Menu

문제

입력

출력

풀이(나의 풀이)

풀이(책 참고)