[알고스팟] QUANTIZE - Quantization / 양자화 (C++)

문제

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

algospot.com :: QUANTIZE

 

풀이

종만북 난이도: 중

 

1000이하의 자연수로 이루어진 수열을 S종류의 1000이하의 정수 값을 사용하여 양자화할 때, 오차 제곱의 합의 최솟값을 구하는 문제이다.

 

1~1000까지의 모든 수에서 10가지만 선택하는 조합의 경우의 수만 해도 너무나 크다. 

따라서 미리 사용할 S(quan_num)개의 수를 선택해서 모든 값과 오차의 제곱을 구해보는 것은 힘들다.

 

따라서 본인은 (start,end)범위의 수열의 값에서 직접 오차 제곱의 합의 최솟값을 구하고 이를 cache_range[start][end]에 저장하는 방법을 택했다.

 

수열의 크기는 최대 100이고 (start,end)범위의 값들을 1~1000의 값들과 오차 제곱의 값을 구해보아야 한다.

따라서 시간 복잡도는 O(N*N*1000)으로 충분히 시간 안에 계산이 가능하다.

 

이때 수많은 반복 연산이 발생하기 때문에 미리 수열 idx번째의 값과 1~1000의 값의 오차 제곱 값을 구해서 cache_squ[idx][num]에 저장해 두자.

for(int idx =0; idx<arr_size ; ++idx)
   for(int num = 1; num <=1000 ; ++num)
      cache_squ[idx][num] = pow(arr[idx] - num ,2);

 

 

cache_range[start][end]는 수열의 start~end까지의 값들의 최소 오차 제곱 값이다.

start== end일 수 있지만(한 가지 수 만을 포함 ) start>end일 수는 없다.

따라서 우리는 start는 end값을 초과하지 않는 경우만 계산하면 된다. (for 문 구성시 start<=end를 조건으로 해주자.)

 

또한 두 가지 이상의 수들에서 최소의 오차 값을 만드는 값은 가장 작은 값과 가장 큰 값의 사이에 있을 수밖에 없다.

이외의 범위의 값을 계산해 보는 것은 의미가 없으므로 num은 arr[start] ~ arr[end]로 제한해서 구하자.

 

최종적으로 num일때 idx: start~end의 값(cache_squ[idx][num])을 모두 더해주고 최솟값을 저장하자.

int min_quan=max_value,sum=0;
    for(int end=0; end<arr_size ; ++end)
      for(int start =0; start<=end ; ++start){
        min_quan = max_value;
 
        for(int num =arr[start]; num<=arr[end] ; ++num){
          sum =0;
          for(int idx = start ; idx<=end ; ++idx)
            sum += cache_squ[idx][num];
          
          min_quan = min(min_quan,sum);
        }
        cache_range[start][end] = min_quan;
      }

 

 

여기서 우리는 어떤 수(num)이 start~end에서의 오차 제곱 합의 최솟값을 만들었는지 알 필요가 없다.

우리가 양자화에 사용 가능한 값은 최대 S(quan_num)개의 종류이다.

위에서 (start,end)범위의 최소 오차 제곱 값을 cache_range[start][end] 에 저장했다.

 

어떤 값이 해당 값을 만들 었는지 알 수는 없지만 1~N(수열의 길이,arr_size)를  최대 S개의 범위로 분할한다고 생각해보자.

1개 범위로 (start=1 ,end =N) 분할할 수도,

2개의 범위로 (start1=1, end1) , (start2=end1+1, end2 =N) 분할 할 수도

S개의 범위로 (start1=1, end1) , (start2=end1+1, end2), ... 분할할 수 도 있다. 

여기서 다른 범위들이 같은 num 값으로 최솟값을 구했을 수도 있지만, 중복된 num을 사용하더라도 최대 S개로 분할한다면 사용된 num의 종류는 S개 이상이 될 수 없다. 따라서 1~S개의 범위로 분할하는 코드를 구현하면 num의 값은 알 필요가 없다.

 

이제 재귀함수 int Quantization(int set_num, int start)

그리고 set_num개의 범위가 결정되었을 때, start부터 새로운 범위 값을 만들 수 있는 경우들의 최솟값을 저장하는

 cache_min[set_num][start] 를 사용하여  1~N을 1~S개의 범위로 분할하는 코드를 구현하자.

 

int Quantization(int set_num, int start){
  if(start >= arr_size)
    return 0;
  
  if(set_num >=quan_num)
    return max_value;
 
  int& ret = cache_min[set_num][start];
  if(ret != -1)
    return ret;
 
  ret = max_value;
  for(int end=start; end<arr_size ; ++end){
    if(set_num<quan_num)
    ret = min(ret, cache_range[start][end]+ Quantization(set_num+1, end+1));
 }//start~end까지를 새로운 범위로 만들고 재귀 호출
 
  return ret;
}
 

이때 max_value의 값은 가능한 결과의 최댓값보다 조금 더 큰 값 1000000100을 사용하였다.

 

까다로웠던 문제이지만 직접 풀어내서 좋지만, 최적화의 길은 멀고도 험하다...

 

코드