알고리즘&자료구조

[종만북] 양자화

아, 그래요? 2022. 11. 3. 12:53

 

1. 문제

문제요약:

양자화란 주어준 수열에서 각 수를 몇개의 수만으로 변환한다. 이때 원래의 수와 변환한 수의 차이의 제곱의 합이 최소가 되도록 해야한다.
길이가 N인 수열을 최대 S개의 수로 양자화할때 원래의 수와 양자화한 수의 오차의 제곱의 합을 구하여라.

 

제한범위:

수열의 길이(N) : 1 ~ 100

양자화에 사용할 숫자의 수(S) : 1~10
각 수는 모두 100이하의 자연수

 

2. 접근 : 단순화

무작위로 정렬된 수열에서 각 수의 양자화 수를 구한다는것은 거의 불가능한 일이다. 각 수마다 양자화할 수 있는 수는 1부터 100까지 존재하고, 양자화 수의 개수 S도 고려해야 한다. 일단 문제를 단순화할 필요가 있다.

 

비슷한 크기의 수들은 같은 수로 양자화된다.

양자화를 하기 위해서는 오차를 최소화해야 하므로 비슷한 크기의 수들은 같은 수로 양자화될 가능성이 높다. 그렇다면 아래와 같은 상황을 생각해보자.

 

오름차순으로 정렬된 수열 a가 있다. a2, a5가 k로 양자화 됐다고 생각해보자. 그렇다면 그 사이에 존재하는 a2, a3, a4는 어떤 수로 양자화 될까?

당연히 k로 양자화 될것이다. 즉, 크기순으로 나열된 수열에서 양자화를 하게 되면 인접한 수들은 같은 수로 양자화 되게 된다.

a(1), a(2), a(3), … a(n)을 x,y,z로 양자화 했다고 하면
x, x, x…,y, y, y, … z, z, z, … 이런 식으로 양자화가 될것이다.

 

문제를 단순화

인접한 수들이 모두 같은 수로 양자화 되는 것을 알게 되었기 때문에 양자화 문제의 접근 방법을 아래와 같인 단순화 할 수 있다.

  1. 수열을 오름차순으로 정렬
  2. 수열을 최대 S개의 부분수열로 분리
  3. 각 부분수열에서 오차의 제곱의 합이 최소가 되는 어떤수 x를 계산
  4. 양자화 수와 원래의 수의 오차의 제곱의 합을 계산

 

3. 풀이

수열 분리하기

양자화 문제에서 가장 핵심이 되는 것이 수열을 최소1개, 최대S개로 분리하는 것이다.
재귀적으로 생각해보자.

 

현재 최대 S개의 부분수열로 분리할 때, 일단 1개의 부분수열을 만들고 남은 수열에서 최대 S-1개의 부분수열로 분리하면 된다.

 

F(start, S) = (start~i 까지의 양자수 x와의 오차의 제곱의 합) + F(i+1, S-1)

 

이를 무식하게 푼다(brute force)고 가정하면,

(C : 조합 함수)


시간복잡도는 위와 같고, N=100 S=10이면 시간복잡도가 10억이 아득히 넘어간다.

 

참고) 왜 저런 시간복잡도가 나옴?
어떤 N개의 수의 수열을 k개의 수열로 분리한다면 결국 수 사이 사이에 k-1개의 파티션을 둔다고 생각할 수 있다. 즉, N-1개의 틈 중, k-1개의 틈을 골라 파티션을 놓으므로 C(n-1,k-1)이 된다. 위 문제에서는 최소 1개에서 최대 S개로 분리하므로 k-1이 1일때부터 S-1일때 까지의 값을 모두 더해야 한다.

 

하지만, 위 문제에서 어떤 i, S에 대하여 F(i, S)는 다른 상황에서 여러번 반복적으로 계산됨을 알 수 있다. 즉, 동적 프로그래밍(Dynamic Programming)을 이용하면 보다 빠르게 문제를 해결할 수 있다.

 

아래 코드는 동적 프로그래밍을 통해 부분수열을 분리하여 양자화하는 코드이다.

int arr[100];
int dp[100][10];

int getMinimumDeviation(int c, int num) {

    if (c == n) {
        return 0;
    }
    if (num == 0) return INF;

    int& ret = dp[c][num];
    if (ret != -1) return ret;
    ret = INF;

    for (int i=c+1; i<=n; ++i) {
        int q = quantizate(c, i-1);
        ret = min(ret, q + getMinimumDeviation(i, num-1));
    }
    return ret;
}
  • 매개변수 : getMinimumDeviation 함수에서 매개변수 c는 부분수열이 시작하는 인덱스로 c부터 마지막 인덱스까지의 부분수열을 다룬다. num은 최대로 분리할 수 있는 개수이다.(예를 들어 num=4면, 현재 주어진 부분수열을 최대 4개로 분리 가능)
  • 기저조건 : 만약 시작 인덱스(c)가 n이면 더 이상 수열이 없고, 분리가 완료된것이므로, 0을 리턴한다. 하지만 만약 아직 수열이 다 분리되지 않았으나, num이 0일 경우, 더 이상 분리가 불가능하므로, 무한대 수를 리턴한다.
  • 재귀 : 현재 수열에서 최대 1개에서 전체로 분리가 가능하므로 각각의 경우에서 구해진 부분수열에 대해 대응하는 양자수를 결정한다. 그리고 남은 부분수열에 대해 같은 함수를 재귀호출한다.

 

양자수 구하기

부분수열을 분리했다면 분리된 수열에 대응하는 양자수를 구해야 한다. 양자수는 수열의 수들과의 오차의 제곱의 합이 최소가 되는 수이다.

양자수는 부분수열의 최솟값과 최댓값 사이에 있으므로 그 값들을 일일히 대입하여 오차의 제곱의 합이 최소가 되는 수를 구할 수도 있겠지만 이는 매우 비효율적이다. 그렇다면 오차의 제곱이 최소가 되는 수를 하나로 한번에 지정할 수 있을까? 아래 수식을 보자.

 


양자수는 수열의 값들의 평균임을 알 수 있다. 하지만 양자수는 정수이므로, 평균이 유리수일 경우, 경계에 있는 두 정수를 모두 조사해줄 필요가 있다. 예를 들어 평균이 3.5라면 3일때와 4일때를 모두 계산하여 오차의 제곱의 합이 더 작은 값을 양자수로 한다.

 

quantizte는 left~right 범위의 부분수열의 양자수를 구한다. 먼저 평균을 구한 후, 평균을 기준으로 경계에 있는 두 값의 오차의 제곱의 합을 구해 더 작은 값을 리턴한다.

int quantizate(int left, int right) {

    int avg = 0;
    for (int i=left; i<=right; ++i) {
        avg += arr[i];
    }

    avg = avg / (right - left + 1);

    int ret = 0;
    for (int i=left; i<=right; ++i) {
        ret += (arr[i] - avg) * (arr[i] - avg);
    }

    avg++;
    int ret2= 0;
    for (int i=left; i<=right; ++i) {
        ret2 += (arr[i] - avg) * (arr[i] - avg);
    }

    ret = min(ret, ret2);
    return ret;
}

 

3. Solution

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int INF = 100000001;
int arr[100];
int n, s;

int dp[100][10];

int min(int x, int y) {
    return x < y ? x : y;
}

int quantizate(int left, int right) {

    int avg = 0;
    for (int i=left; i<=right; ++i) {
        avg += arr[i];
    }

    avg = avg / (right - left + 1);

    int ret = 0;
    for (int i=left; i<=right; ++i) {
        ret += (arr[i] - avg) * (arr[i] - avg);
    }

    avg++;
    int ret2= 0;
    for (int i=left; i<=right; ++i) {
        ret2 += (arr[i] - avg) * (arr[i] - avg);
    }

    ret = min(ret, ret2);
    return ret;
}

int getMinimumDeviation(int c, int num) {

    if (c == n) {
        return 0;
    }
    if (num == 0) return INF;

    int& ret = dp[c][num];
    if (ret != -1) return ret;
    ret = INF;

    for (int i=c+1; i<=n; ++i) {
        int q = quantizate(c, i-1);
        ret = min(ret, q + getMinimumDeviation(i, num-1));
    }
    return ret;
}

int main() {

    int tc;
    cin >> tc;

    for (int c=0; c<tc; ++c) {
        cin >> n >> s;
        for (int i=0; i<n; ++i) {
            cin >> arr[i];
        }
        sort(arr, arr+n);

        memset(dp, -1, sizeof(dp));

        cout << getMinimumDeviation(0, s) << endl;
    }
}