[동적 계획법] Quantization

1. 완전 탐색 알고리즘

 

이 문제는 입력으로 주어진 배열을

먼저 정렬해야한다.

 

정렬을 하고나면 이 문제는 간단히 풀 수 있다.

어떤 구간에서 평균값이 오차의 최소값이므로

우리는 부분문제를 평균값과 오차의 제곱 합을 따로

구할 수 있는 함수를 구현만하면 된다.

     

                            end

quant(begin) = min(quant(hi)+ quantization(begin, hi))  

      begin = 0        hi = 1                   

 

quantization(begin, hi)는 begin부터 hi까지 배열의 평균값 오차의 제곱 합을 반환하는 함수이다.

 

2. 메모이제이션 적용

 

       Cache[begin][usednum]

                 = usednumb만큼 양자화를 수행한 상태에서

                    begin으로 시작하는 배열의 양자화 오차 제곱의 합의 최소값을 가짐

                    

usednumb만큼 배열을 나눈 상태에서 begin으로 시작하는 배열은

그 이전의 수행과 독립이므로

이 함수는 최적 부분 구조가 성립한다고 볼 수 있다.

따라서 이 문제는 동적계획법으로 문제를 해결할 수 있다.

 

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
 
int cache[1000][10];
int seq[1000];
 
int quantization(int lo, int hi)
{
    int average = 0, ret = 0;
   
    for(int i = lo; i < hi; i++)
        average += seq[i];
   
    average = ((double) average/(hi-lo)) + 0.5;
   
   for(int i = lo; i < hi; i++)
       ret =  ret + (average - seq[i])*(average - seq[i]);
   return ret; 
}
 
int quant(int lo, int usednum, int s, int seqN)
{
    int &ret = cache[lo][usednum];
    if(ret != -1) return ret;
    if(lo == seqN) return 0;
    if(usednum == s) return 12345678;
 
    ret = 12345678;
 
    for(int hi = lo + 1; hi <= seqN; hi++)
        ret = std::min(quantization(lo, hi) + quant(hi, usednum + 1,s,seqN), ret);
 
    return ret;
}
 
int main()
{
    int testCase = 0;
    int seqN = 0;
    int usenum = 0;
 
    std::cin>>testCase;
    for(int i = 0; i < testCase; i++)
    {
        memset(cache, -1, sizeof cache);
        std::cin>>seqN>>usenum;
        
        for(int j = 0; j < seqN; j++)
            std::cin>>seq[j];
        
        std::sort(seq, seq+seqN);
        std::cout<<quant(0, 0,usenum, seqN)<<std::endl;
    }
}

 

3. 더 빨리 풀 수 있는지?

 

책에서는 기초 수학을 이용하여 이 문제를 더 빠르게 수행가능한 함수를 구현하였다.

오차 제곱의 합

오차의 제곱 합을 식으로 세운뒤

이 식을 풀어보면 이차함수가 나온다.

이차 함수를 미분한 식이 0이되는 해는 이차함수의 극점의 좌표 x값이 된다.

미분

평균일 때 최소값을 구할 수 있다.

이를 통해 평균을 사용하면 오차를 최소화 할 수 있다는 사실을 알 수 있다.

여기서 더 나아가 부분합을 이용하게되면 o(1)만에 수행되는 quantization()함수를 구현할 수 있다.

 

 

 

배열을 입력받고 정렬한뒤 psum 과 제곱의 psum 을

O(n)의 전처리 한번에 구하고 나면 우리는

quantization()함수를 O(1) 만에 수행할 수 있게된다.

 

(m = psum/b-a+1 )

 

따라서 알고리즘의 전체 시간 복잡도는 부분문제의 수 O(ns) 에

각 부분 문제의 답을 계산하는데 드는 시간O(n)을   (for문)

곱한 O(n^2s)가 된다.

 

책의 풀이를 보고 수학적으로 증명하는 것이 중요하다 생각하였다.

 

 

quantization