[c++] 알고리즘 문제 해결 전략 1권 :: Quantization[양자화] (코드, 알고리즘)

Quantization

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

나의 답

알고리즘

1. 수열을 정렬한다.
2. 부분 수열들의 경우의 수를 돌면서 부분 수열의 오차합이 가장 적은 수열을 구한다.

2번 과정에 대해서 최적부분구조임을 발견하고 각 부분 수열의 오차합을 메모이제이션하는 방식으로 진행하여야한다. 하지만 본인은 메모이제이션을 부분 수열을 모두 완성했을 때 진행하는 식으로 하여 어쨌든 부분 수열을 만드는 재귀함수의 끝에 도달해야 메모이제이션을 쓸 수 있게 구현하였다. 이 점이 시간초과의 원인이 되었다고 생각한다.

코드

코드1

#include <iostream>
#include <algorithm>

using namespace std;

int N, S;
int arr[100];
int* num_idx; // index 0은 -1, 1 ~ S까지 있음
int min_res = 1e9;
int memorize[101][101];

void Quantization(int n) { // 나눈 횟수
    if (n == S - 1) {
        int start = 0; int end;
        int res = 0;
        for (int i = 1; i < S; i++) {
            end = num_idx[i];
            if (memorize[start][end] != -1) {
                res += memorize[start][end];
                start = end + 1;
                continue;
            }

            int mid = 0;
            for (int j = start; j <= end; j++) {
                mid += arr[j];
            }

            mid /= (end - start + 1);
            int mid_arr[3] = { mid - 1,mid,mid + 1 };
            int tmp;
            int min_mid = 1e9;
            for (int j = 0; j < 3; j++) {
                tmp = 0;
                for (int k = start; k <= end; k++) {
                    tmp += (int)pow(mid_arr[j] - arr[k], 2);
                }
                min_mid = min(tmp, min_mid);
            }
            res += min_mid;
            memorize[start][end] = min_mid;
            start = end + 1;
        }

        end = N - 1;
        if (memorize[start][end] != -1) {
            res += memorize[start][end];
        }
        else {
            int mid = 0;
            for (int i = start; i <= end; i++) {
                mid += arr[i];
            }
            mid /= (end - start + 1);
            int mid_arr[3] = { mid - 1,mid,mid + 1 };
            int tmp;
            int min_mid = 1e9;
            for (int i = 0; i < 3; i++) {
                tmp = 0;
                for (int j = start; j <= end; j++) {
                    tmp += (int)pow(mid_arr[i] - arr[j], 2);
                }
                min_mid = min(tmp, min_mid);
            }
            memorize[start][end] = min_mid;
            res += min_mid;
        }

        if (res < min_res)
            min_res = res;
        return;
    }
    for (int i = num_idx[n] + 1; i < N - (S - n - 1); i++) {
        num_idx[n + 1] = i;
        Quantization(n + 1);
    }
}

int main() {
    int C;
    cin >> C;
    int ans[50];

    int index = 0;
    while (C--) {
        cin >> N >> S;
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }

        fill(&memorize[0][0], &memorize[100][101], -1);
        sort(&arr[0], &arr[N]);
        min_res = 1e9;
        num_idx = (int*)malloc(sizeof(int)*(S));
        num_idx[0] = -1;

        Quantization(0);

        ans[index++] = min_res;
        delete num_idx;
    }
    for (int i = 0; i < index; i++)
        cout << ans[i] << endl;
}

시간 초과

코드2

#include <iostream>
#include <algorithm>

using namespace std;

int N, S;
int arr[100];
int* num_idx; // index 0은 -1, 1 ~ S까지 있음
int min_res = 1e9;
int memorize[101][101];

int pSum[101], pSqSum[101];

void precalc() {
    pSum[0] = arr[0];
    pSqSum[0] = arr[0] * arr[0];
    for (int i = 1; i < N; ++i) {
        pSum[i] = pSum[i - 1] + arr[i];
        pSqSum[i] = pSqSum[i - 1] + arr[i] * arr[i];
    }
}

void Quantization(int n) { // 나눈 횟수
    if (n == S - 1) {
        int start = 0; int end;
        int res = 0;
        for (int i = 1; i < S+1; i++) {
            end = num_idx[i];
            if (i == S)
                end = N - 1;
            if (memorize[start][end] != -1) {
                res += memorize[start][end];
                start = end + 1;
                continue;
            }

            int sum = pSum[end] - (start == 0 ? 0 : pSum[start - 1]);
            int sqSum = pSqSum[end] - (start == 0 ? 0 : pSqSum[start - 1]);
            int m = int(0.5 + (double)sum / (end - start + 1));
            int tmp_res = sqSum - 2 * m*sum + m * m*(end - start + 1);
            memorize[start][end] = tmp_res;
            res += tmp_res;
            start = end + 1;
        }

        if (res < min_res)
            min_res = res;
        return;
    }
    for (int i = num_idx[n] + 1; i < N - (S - n - 1); i++) {
        num_idx[n + 1] = i;
        Quantization(n + 1);
    }
}

int main() {
    int C;
    cin >> C;
    int ans[50];

    int index = 0;
    while (C--) {
        cin >> N >> S;
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }
        if (S >= N) {
            ans[index++] = min_res;
        }
        else {
            fill(&memorize[0][0], &memorize[100][101], -1);
            sort(&arr[0], &arr[N]);
            min_res = 1e9;
            num_idx = (int*)malloc(sizeof(int)*(S));
            num_idx[0] = -1;
            precalc();

            Quantization(0);

            ans[index++] = min_res;
            delete num_idx;
        }
    }
    for (int i = 0; i < index; i++)
        cout << ans[i] << endl;
}

index를 사용하고, 사용한 part 수를 기록해서 메모이제이션하기가 어려웠다.

 코드 1과 코드 2의 차이는 오차 제곱의 합을 구하는 시간을 줄여준 것뿐이다. 이는 시간 초과를 해결해주지 못했는데, 그 이유는 해당 코드에서는 memoization을 파트로 다 쪼갰을 때 (모든 부분 수열이 나왔을 때) 적용 시킬 수 있기 때문에 어떤 경우에건 모든 부분 수열을 구하긴해야한다. 즉, 재귀의 기저사례까지 반드시 가야하는 것이다. 이렇게 구현하였으니 재귀의 호출 수가 줄지 않아 시간 초과가 나올 수 밖에 없다.

 

 본인이 놓친 부분은 해당 문제가 최적부분구조이며 이를 이용해서 재귀함수를 구현하면 현재 위치에서 남은 파트 수를 가지고 값이 저장되어있다면 재귀를 더이상 부르지 않아도 되게끔 실행가능하다는 것이다.

 

정답코드

#include <iostream>
#include <algorithm>

using namespace std;

int N, S;
int arr[100];
int memo[101][11];

int pSum[101], pSqSum[101];
// pSum : idx까지의 요소 합 // pSqSum : idx까지의 요소^2의 합

void precalc() { // pSum, pSqSum 구하기
    pSum[0] = arr[0];
    pSqSum[0] = arr[0] * arr[0];
    for (int i = 1; i < N; ++i) {
        pSum[i] = pSum[i - 1] + arr[i];
        pSqSum[i] = pSqSum[i - 1] + arr[i] * arr[i];
    }
}

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 = int(0.5 + (double)sum / (hi - lo + 1)); // 평균 반올림해서 계산

    int ret = sqSum - 2 * m*sum + m * m*(hi - lo + 1); // 공식에 대입
    return ret;
}

int Quantization(int from, int parts) {
    if (from == N) return 0; // 모든 수를 양자화했을 때 => S가 N보다 클 때
    if (parts == 0) return 1e9; // 모든 묶음을 다 썼을 때 => 아주 큰 수 return
    int& ret = memo[from][parts];
    // from부터의 요소를 parts개의 묶음으로 묶는 최소의 오차합을 저장
    if (ret != -1) return ret;
    ret = 1e9;

    for (int partSize = 1; from + partSize <= N; partSize++) {
        // 각 묶음마다 1개부터 N-현재idx 개까지 원소를 가지면서
        ret = min(ret, minError(from, from + partSize - 1) + Quantization(from + partSize, parts - 1));
        // 다음 묶음들의 오차 + 현재 오차 계산
    }

    return ret;
}

int main() {
    int C;
    cin >> C;
    int ans[50];

    int index = 0;
    while (C--) {
        cin >> N >> S;
        for (int i = 0; i < N; i++) {
            cin >> arr[i];
        }

        fill(&memo[0][0], &memo[100][11], -1);
        sort(&arr[0], &arr[N]);
        precalc();
        ans[index++] = Quantization(0,S);
    }
    for (int i = 0; i < index; i++)
        cout << ans[i] << endl;
}

 정답 코드는 from에서 parts개의 부분 수열을 만들어내는 최소 부분합을 메모이제이션하는 형태로 코드를 구현하였다. 또한 오차제곱의 합을 매번 계산해도 시간초과는 되지 않지만 입력범위가 최대 100개의 수밖에 되지 않았기 때문에 모든 경우의 수를 저장해두는 메모이제이션을 통해서 O(1)의 시간복잡도로 오차합을 계산할 수 있게 하였다.

pSqSum과 pSum을 미리 다 구해놓는 방식을 사용!

 

+) 반올림은 다음과 같이 표현하였다.

반올림 수 = (int)(0.5 + 기존 수); // 해당 수에 0.5를 더한 후 내림하는 방법

 

 

시간복잡도

 최악의 경우 시간복잡도를 생각해보자.

 우선 테스트케이스가 50개이므로 50 * (Quantization 함수의 시간복잡도) 가 총 시간복잡도이다. fill이나 sort, precalc 함수는 Qunatization 함수보다 복잡도가 낮으므로 생략하였다.

 Quantization 함수는 재귀적으로 S가 10일 때 10단계까지 들어갈 수 있으며, N개의 수를 S묶음으로 분할하는 경우의 수가 (n-1)Cs 이므로 최대 99C9로 나타낼 수 있다.

N개의 수 사이의 간격이 N-1개이므로, 이 중 S-1개를 선택하면 N개의 수를 S개의 set으로 나눌 수 있다.

if문으로 함수 초반에 return 되는 것들은 minError 계산을 거치지 않으므로 생략해주었다.

minError는 매번 계산 시에는 시간복잡도가 많이 들겠지만, 해당 방법에서 미리 계산을 해두었기 때문에 O(1)의 시간복잡도를 가진다.

 

 99C9는 2*10^12 정도이므로 memorization을 쓰지 않았을 때의 시간복잡도는 최대 50(테스트케이스)*(2*10^12)(가능한 묶음 경우의 수)*1(minError복잡도) = 10^14 이므로 시간 내에 실행할 수 없다.

=> brute force 시간 복잡도 : 10^14

 하지만 memorization 기법을 사용하였기 때문에 각 index별로 S개만 조사하면 된다. 정확히 얘기하면 뒤에서 10개까지는 가능한 S의 갯수에 따라서, 10개부터는 S가 1~10개 모두 조사 가능하다. 즉, 아래 그림처럼 경우의 수가 생길 수 있다.

 따라서 index(뒤에서부터) 1~10은 1에서 10까지 더한 것이므로 55 + 11~100은 계속 10개의 경우의 수가 생기므로 90*10 = 900 해서 총 약 1000번의 연산이 필요하다. 이후 겹치는 연산들은 메모이제이션으로 해결가능하다.

=> 최종 시간 복잡도 : 10^3

 

테스트케이스

1
9 3
1 2 3 4 6 9 10 12 13
=> 14

1
9 3
1 2 3 4 6 8 9 10 13
=> 15

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

5
9 4
78 76 41 5 3 15 9 81 5
2 3
1 2
10 2
1 7 1 7 2 9 2 9 3 10
17 6
12 45 7 9 78 456 521 789 951 123 457 159 145 764 15 63 21
5 2
1 2 3 4 5

=> 33 0 11 4413 6

 

깨달은 점

1. 다이나믹 프로그래밍은 모든 경우의 수를 미리 저장해놓는 방식으로도 사용 가능하다.

2. 다이나믹 프로그래밍이 가능한 방식에서는 최적부분구조에 해당하는 지 꼭 살펴보자.

   => 해당한다면 코드가 훨씬 쉬워진다.

   (단계 별로 잘라서 메모이제이션 가능)

3. 메모이제이션은 문제에서 제시했듯이 주소를 받아와서 처리하는 방법이 가장 이상적이다.

4. 문제를 마주했을 때 어떤 방식으로 부분 문제를 자르는 것이 가장 메모이제이션 하기 좋고 간단하게 표현 가능한지 생각하고 구현하자.