[알고스팟] Quantization

 

 

문제 링크

 

Quantization

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • QUANTIZE
  • 3000ms
  • 65536kb
  • 3800
  • 1215 (31%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 연습문제
  • 보기

문제

 

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 개의 수로 양자화할 때 오차 제곱의 합의 최소값을 출력한다.

 

예제 입력

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

 

어떻게 풀까?

 

위 문제는 주어진 배열만으로 양자화를 진행하기 보다는 데이터를 정렬해서 보는 것이 굉장히 편합니다.

양자화라는 것은 결국 비슷한 숫자를 특정한 부분에 매핑시키는 것이기 때문에, 데이터를 정렬하면 결국 양자화된 값도 정렬된 상태로 존재하게 됩니다. 

따라서, 만약 데이터를 정렬한다면, 이 문제는 해당 구간을 어떻게 s개로 나누고, 각 부분에 1~1000 중에서 어떤 숫자를 넣을지 완전 탐색을 하는 문제로 바꿀 수 있는 것입니다!

 

큰 틀을 잡았으니

이번에는, s개의 부분으로 나눴다고 가정해서, 각 s에는 어떤 수를 넣어야 최소의 값이 나올지 생각해봅시다.

오차 제곱의 합이기 때문에 아래와 같은 수식으로 나타낼 수 있습니다.

 

 

위 식은 m에대한 2차 함수로, 2차항의 계수 (b - a + 1)이 양수이기 때문에 미분을 통해서 그 최솟값을 구할 수 있습니다!

2 차 함수가 아래로 볼록일 때, 함수의 최솟값은 미분 값이 0 에 가까운 곳이기 때문입니다.

 

식을 미분하면

이고, 이를 m에 대해서 정리하면,

 

 

을 얻을 수 있습니다. 계산하고 보니, 결국 구간의 평균값임을 알 수 있습니다! 

A[i]까지 배열의 합을 O(1) 만에 해결하기 위해 부분합 공식을 이용합시다.

 

 부분합을 이용해서 어떤 배열 pSum[i]라는 배열에 A[0] ~ A[i] 까지의 합을 저장하는 배열을 만든다면,

 

는 A[b] - A[a-1]을 통해 구할 수 있습니다. 이를 이용하면, 부분 문제의 오차 제곱도 O(1) 시간에 구할 수 있습니다.

 

참고로, pSum에서 A[0]~A[0]까지의 합을 구하기 위해서는 pSum[0] - pSum[-1]을 계산해야하기 때문에,

A의 인덱스를 1 부터 시작하게 하고, pSum[0] = 0 으로 둔다면 훨씬 쉽고 일반적으로 구간합을 구할 수 있게 됩니다!

 

 

 

 

위 : A[i], 아래 : pSum[i] = (A[0]에서 A[i+1]까지의 합)

 

위의 식을 보면 pSum[3] - pSum[1] = 6 - 3 = 3 이고, 이는 A[3] + A[2]의 값임을 알 수 있습니다.

 

 

 

 

이제 다시 s개의 부분을 나눠서 어떻게 하면 좋을지 생각해봅시다.

우선, 앞에서 어떠한 경로로 왔던지 간에, 한 부분 집합을 몇개로 양자화 하는지 같다면, 그 결과 값은 같습니다. (최적 부분 구조)

 

예를 들면, {1,2,3,5,9,18,22} 가 주어지면, {3,5,9,18,22} 로 오기전에 양자화 된 숫자만 같다면, {1,2}를 어떻게 양자화 하던지는 상관이 없습니다.

{3,5,9,18,22} 을 2 개의 서로 다른 숫자로 양자화 한다는 조건만 있다면, 앞의 부분은 상관이 없다는 것 입니다!

하지만, {3,5,9,18,22}을 3 개의 서로 다른 숫자로 양자화 하거나, 1 개의 숫자로만 양자화 한다면, 최적 오차의 값이 달라질 것 입니다.

 

따라서, 메모이제이션에는 해당 부분집합이 어디서 부터인지 시작하는지에 대한 정보와, 몇 개의 부분으로 나눌 수 있는지에 대한 정보 2개를 이용하도록 합니다.

 

그렇다면 이제 아래의 코드를 통해 어떻게 이 생각을 코드로 작성하는지 알아봅시다!

 

코드

 

#pragma once
#include<cstdio>
#include<cstring>
 
// Quantization
// 알고스팟
// https://algospot.com/judge/problem/read/QUANTIZE
 
int nums[101] = { 0 }, n, s;
int temp[101], memoi[11][101];
const int INF = 987654321;
int pSum[101] = { 0 }, p2Sum[101] = { 0 };
 
int min(int i1, int i2)
{
    return i1 < i2 ? i1 : i2;
}
 
void merge(int left, int m, int right)
{
    int l = left, r = m + 1, k = left;
 
    while (l <= m && r <= right)
    {
        if (nums[l] < nums[r])
        {
            temp[k++] = nums[l++];
        }
        else
        {
            temp[k++] = nums[r++];
        }
    }
 
    while (l <= m) temp[k++] = nums[l++];
    while (r <= right) temp[k++] = nums[r++];
 
    for (int i = left; i <= right; i++)
    {
        nums[i] = temp[i];
    }
}
 
void mergeSort(int left, int right)
{
    if (left < right)
    {
        int m = (left + right) / 2;
        mergeSort(left, m);
        mergeSort(m + 1, right);
 
        merge(left, m, right);
    }
}
 
int sMin(int left, int right)
{
    int m = (int)((double(pSum[right] - pSum[left - 1])) / (right - left + 1) + 0.5);
 
    return p2Sum[right] - p2Sum[left - 1] - 2 * (pSum[right] - pSum[left - 1]) * m + m * m * (right - left + 1);
}
 
int getMin2(int cnt, int idx)
{
    int &ret = memoi[cnt][idx];
 
    if (ret != -1)
    {
        return ret;
    }
 
    if (idx == n)
    {
        return ret = 0;
    }
 
    if (cnt == 1)
    {
        return ret = sMin(idx, n);
    }
 
    ret = INF;
 
    for (int next = idx + 1; next <= n; next++)
    {
        ret = min(ret, sMin(idx, next - 1) + getMin2(cnt - 1, next));
    }
    
    return ret;
}
 
void init()
{
    scanf("%d %d\n", &n, &s);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d \n", &nums[i]);
    }
 
    mergeSort(1, n);
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    while (t--)
    {
        init();
 
        int res = INF;
        memset(memoi, -1, sizeof(memoi)); 
        memset(pSum, 0, sizeof(pSum));
        memset(p2Sum, 0, sizeof(p2Sum));
 
        for (int i = 1; i <= n; i++)
        {
            pSum[i] += pSum[i - 1] + nums[i];
            p2Sum[i] += p2Sum[i - 1] + nums[i] * nums[i];
        }
 
        res = getMin2(s, 1);
        
        printf("%d\n", res);
    }
 
    return 0;
}

 

여담

 

생각보다 어려웠습니다! 특히, 부분합에서 평균을 구하면 손쉽게 어떤 수로 양자화해야지 안다는 생각을 못해서 너무 너무 시간이 오래걸렸습니다. 저는 처음에... 1부터 1천까지 다 넣으면서 최소의 값을 구했었습니다... 그래서 풀리긴 했지만 시간이 굉장히 오래걸렸습니다.

 

해당 방법의 시간 복잡도를 구해봅시다. 시간 복잡도는 부분 문제의 개수가 ns개 이고, 부분 집합에 반복문이 하나 있기 때문에 

의 시간이 걸립니다.