algospot.com - 양자화(Quantization) 문제
요즘 회사 내에서 몇 명이 모여 다음의 책을 주제로,
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 세트 전2권
; http://www.yes24.com/24/goods/8006522
스터디를 하고 있습니다. 진행 방식이, 답을 안 보고 우선 문제를 어떻게든 풀어오는 것인데 그러다 보니 다양한 의견들이 모입니다. ^^
오늘은 그중에서, algospot.com의 Quantization 문제를 잠깐 소개하겠습니다.
Quantization
; https://algospot.com/judge/problem/read/QUANTIZE
위의 문제를 푸는 2가지 포인트가 있는데, 하나는 제곱의 오차를 빠르게 구하는 것이고, 다른 하나는 구간을 잡는 것입니다.
여기서 제곱의 오차를 구하는 것은, 지정된 구간 내에 양자화된 숫자 하나를 골라야 하는 문제가 있습니다. 예를 들어 다음의 수열에서,
1 9 9 9 9
1개의 양자화된 숫자를 골라야 한다면 7이어야 하고 그래서 최소 오차 제곱이 36 + 4 + 4 + 4 + 4 = 52가 됩니다.
재미있는 것은, 이 7이라는 숫자를 고르는데 1명은 그 값을 직접 구하는 것을 몰라 1 ~ 9 범주 내의 모든 수를 대입해서 7을 구하도록 하는 반면 나머지 3명은 그것이 숫자 5개의 평균값이라는 것을 알았습니다. 문제는? ^^ 그 한 명이 나머지 3명에게 왜 평균값이 양자화된 숫자의 최적 값인지를 아느냐... 라고 질문했을 때 아무도 제대로 된 답변을 하지 못 했습니다. 그냥 약간의 숫자 테스트를 통한 경험으로 알고 있을 뿐! (책에, 그 이유가 나오는데 구간 수열에 대해 미분을 하면 최소 오차 제곱의 합은 평균 값이라고.)
제가 바로 그 3명 중의 하나였는데 그래서 다음과 같이 지정한 구간 내의 평균값으로 최소 오차 제곱을 구하는 함수를 만들어 두었습니다.
int g_squareSumCache[MAX_N][MAX_N];
int calcSquareSum(int start, int end)
{
int &sum = g_squareSumCache[start][end];
if (sum == -1)
{
int partialSum = 0;
for (int i = start; i <= end; i++)
{
partialSum += g_seq[i];
}
int quantizeNumber = round(partialSum / (end - start + 1.0));
int squareSum = 0;
for (int i = start; i <= end; i++)
{
int diff = (g_seq[i] - quantizeNumber);
squareSum += (diff * diff);
}
sum = squareSum;
}
return sum;
}
그다음, 구간을 잡는 문제인데요. 책의 해답이 예술입니다. ^^
int calc(int start, int quantizeCount)
{
if (start == g_seqCount)
{
return 0;
}
if (quantizeCount == 0)
{
return g_INFINITE;
}
int &minSum = g_cache[start][quantizeCount];
if (minSum != -1)
{
return minSum;
}
minSum = g_INFINITE;
for (int partitionSize = 1; start + partitionSize <= g_seqCount; partitionSize++)
{
minSum = min(minSum,
calcSquareSum(start, start + partitionSize - 1) + calc(start + partitionSize, quantizeCount - 1));
}
return minSum;
}
위와 같이 재귀적으로 for 문을 돌면 정말 모든 구간을 열람하게 됩니다. 예를 들어, "1 2 3 4 5 6 7 8 9 10" 수열에서 3개의 양자화된 숫자를 사용하는 상황이라면, 첫 번째 재귀에서 다음과 같이 시도하고,
[0~0] + [1...10]
[1...10] == [1~1], [1~2], [1~3], [1~4], [1~5], [1~6], [1~7], [1~8], [1~9], [1~10]
두 번째 재귀의 [1~1]로 다시 들어가면 이렇게 구간 열람이 됩니다.
[0~0] [1~1] + [2...10]
[2...10] == [2~2], [2~3], [2~4], [2~5], [2~6], [2~7], [2~8], [2~9], [2~10]
즉, 다음과 같이 나열되는 것입니다.
[0~0] [1~1] [2~2]
[0~0] [1~1] [2~3]
[0~0] [1~1] [2~4]
[0~0] [1~1] [2~5]
[0~0] [1~1] [2~6]
[0~0] [1~1] [2~7]
[0~0] [1~1] [2~8]
[0~0] [1~1] [2~9]
[0~0] [1~1] [2~10]
물론 위의 열람 중에서 [0~0] [1~1] [2~2] 경우에는 수열에서 "1, 2, 3"만을 양자화하려는 시도이기 때문에 필요 없는 호출이긴 합니다. 그래서 얼핏 보면 비효율적인 열람 방법인 것처럼 보이는데 memoization 역할을 하는 g_cache 덕분에 O(N * N)의 시간 복잡도로 마무리가 됩니다.
마침, 이 문제를 스터디하는 동안 algospot의 채점 시스템에 오류가 발생해서 우리 4명의 스터디 인원은 각자의 답으로 모이게 되었습니다. 그리고 제 경우에는 아쉽게도 책에 적힌 구간별 점화식을 생각해 내지 못하고 Quick Sort처럼 분할 정복하는 식으로 답을 냈는데, .... 오답이었습니다. ^^;
책의 내용을 보고 나서야, 그렇게 구간별로 모든 시도를 해보는 것에 감탄을 했었는데요. 그러다 문득 이런 생각이 드는 것입니다. 과연, algospot의 채점 시스템이 살아 있어서 오답인 것을 스터디 전에 알았다면 다음의 시도로 나는 무엇을 해볼 수 있었을까??? 하는 것입니다.
그런 맥락으로 다시 문제를 풀었습니다.
개인적으로, 그다음 후보로 아마 "
조합"을 생각해 냈을 것입니다. 사실, 조합은 다음의 글에서도 썼지만 여러 더미로 파티션하는 데에도 사용할 수 있는 성질이 있습니다.
동전을 여러 더미로 나누는 경우의 수 세기(Partition Number) - 두 번째 이야기
; https://www.sysnet.pe.kr/2/0/1719
그래서 조합으로 양자화 문제를 풀면 다음과 같이 코드를 낼 수 있습니다.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
using namespace std;
#define MAX_N 100
#define QUANTIZE_MAX_N 10
int g_seq[MAX_N];
int g_seqCount;
int g_quantizeCount;
int g_INFINITE = numeric_limits<int>::max() / 2;
class Partition
{
int _n;
int _k;
vector<int> _indexList;
vector<int> _elements;
int _cache[QUANTIZE_MAX_N][MAX_N];
int _minSum = g_INFINITE;
int _squareSumCache[MAX_N][MAX_N];
public:
Partition(int elems[], int elemSize, int partitionCount)
{
_elements.insert(_elements.begin(), &elems[0], &elems[elemSize]);
_n = elemSize;
_k = partitionCount - 1;
memset(_cache, -1, sizeof(int) * QUANTIZE_MAX_N * MAX_N);
memset(_squareSumCache, -1, sizeof(int) * MAX_N * MAX_N);
if (_k == 0)
{
_minSum = calcSquareSum(0, elemSize);
}
else
{
_indexList.resize(_k);
int i = 0;
for (i = 0; i < _k; i++)
{
_indexList[i] = i;
}
_indexList[i - 1] --;
Enumerate();
}
}
bool Enumerate()
{
int sum = 0;
int startIndex = 0;
int endIndex = _elements.size() - 1;
int i;
if (_indexList.size() == 0 || _indexList[0] == _n - _k)
{
return false;
}
for (i = _k - 1; i > 0 && _indexList[i] == _n - _k + i; i--)
{
}
_indexList[i] ++;
for (int j = i; j < _k - 1; j++)
{
_indexList[j + 1] = _indexList[j] + 1;
}
for (int calcIndex = 0; calcIndex <= i; calcIndex++)
{
sum += calcSquareSum(startIndex, _indexList[calcIndex]);
startIndex = _indexList[calcIndex];
}
int partialSum = 0;
int squareSum = 0;
for (int calcIndex = i + 1; calcIndex < _indexList.size(); calcIndex++)
{
squareSum = calcSquareSum(startIndex, _indexList[calcIndex]);
partialSum += squareSum;
sum += squareSum;
startIndex = _indexList[calcIndex];
}
squareSum = calcSquareSum(startIndex, endIndex + 1);
partialSum += squareSum;
sum += squareSum;
_minSum = min(_minSum, sum);
return true;
}
int GetResult()
{
return _minSum;
}
int calcSquareSum(int start, int end)
{
if (start == end - 1 && end == _elements.size())
{
return 0;
}
int &sum = _squareSumCache[start][end];
if (sum == -1)
{
int partialSum = 0;
for (int i = start; i < end; i++)
{
partialSum += _elements[i];
}
int quantizeNumber = round(partialSum / ((double)end - start));
int squareSum = 0;
for (int i = start; i < end; i++)
{
int diff = (_elements[i] - quantizeNumber);
squareSum += (diff * diff);
}
sum = squareSum;
}
return sum;
}
};
// https://algospot.com/judge/problem/read/QUANTIZE
int main()
{
int cases;
cin >> cases;
for (int i = 0; i < cases; i++)
{
int productSequare = 0;
cin >> g_seqCount;
cin >> g_quantizeCount;
set<int> numbers;
memset(g_seq, 0, sizeof(int) * MAX_N);
for (int j = 0; j < g_seqCount; j++)
{
cin >> g_seq[j];
numbers.insert(g_seq[j]);
}
if (numbers.size() <= g_quantizeCount)
{
cout << productSequare << endl;
continue;
}
sort(g_seq, g_seq + g_seqCount);
{
Partition c(g_seq, g_seqCount, g_quantizeCount);
while (c.Enumerate() == true);
cout << c.GetResult() << endl;
}
}
return 0;
}
하지만, 조합만으로 이 문제를 풀면 경우의 수가 너무 많은데 일례로 100개의 수열이 있고 10개의 양자화 수를 내야 한다면 "C(n,r) = 99C9"가 되어 무려 1,731,030,945,644라는 어마어마한 수가 나옵니다.
그래도 잘 생각해 보면 조합도 값의 일부를 cache할 수 있는 여지가 있습니다. 가령 4C3인 경우를 보면,
0, 1, 2,
0, 1, 3,
0, 1, 4,
0, 2, 3,
0, 2, 4,
0, 3, 4,
1, 2, 3,
1, 2, 4,
1, 3, 4,
2, 3, 4,
라고 나오는데, 마지막 3번째의 [x, x, 2], [x, x, 3], [x, x, 4]는 모두 반복적으로 나와서 그 구간의 파티션 값은 cache하는 경우 나중에 그대로 쓸 수 있습니다. 또한, 2번째 구간을 포함하는 "x, 2, 3", "x, 2, 4"에서도 "[2, 3], [2, 4]" 구간은 나중에도 "1, 2, 3", "1, 2, 4" 등에서 나오기 때문에 재사용이 가능합니다.
물론, 재사용하는 것에만 그치면 안 됩니다. 그렇게 되면 마찬가지로 모든 경우의 수를 열람하는 것이기 때문입니다.
따라서, 반복적으로 나오는 구간에 대해 건너뛰는 것도 필요합니다. 가령 위의 4C3에서 다음의 계산을 마쳤으면,
0, 1, 2,
0, 1, 3,
0, 1, 4,
0, 2, 3,
0, 2, 4,
이후, "1, 2, 3" 조합으로 나아갔을 때 이전의 "0, [2,3]", "0, [2,4]"에서 최소 제곱 오차가 있었던 값이 미리 cache되어 있다면 "1, 2, 3", "1, 2, 4"의 조합을 일일이 해보지 않고서도 "1, 2, 3"에서 "1, 3, 4"로 넘어가는 것이 가능합니다.
첫 번째 조합 코드에서 그런 처리를 추가한 것이 다음의 코드입니다. (굵은 파란색 코드가 추가된 부분)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <cstring>
using namespace std;
#define MAX_N 100
#define QUANTIZE_MAX_N 10
int g_seq[MAX_N];
int g_seqCount;
int g_quantizeCount;
int g_INFINITE = numeric_limits<int>::max() / 2;
class Partition
{
int _n;
int _k;
vector<int> _indexList;
vector<int> _elements;
int _cache[QUANTIZE_MAX_N][MAX_N];
int _minSum = g_INFINITE;
int _squareSumCache[MAX_N][MAX_N];
public:
Partition(int elems[], int elemSize, int partitionCount)
{
_elements.insert(_elements.begin(), &elems[0], &elems[elemSize]);
_n = elemSize;
_k = partitionCount - 1;
memset(_cache, -1, sizeof(int) * QUANTIZE_MAX_N * MAX_N);
memset(_squareSumCache, -1, sizeof(int) * MAX_N * MAX_N);
if (_k == 0)
{
_minSum = calcSquareSum(0, elemSize);
}
else
{
_indexList.resize(_k);
int i = 0;
for (i = 0; i < _k; i++)
{
_indexList[i] = i;
}
_indexList[i - 1] --;
Enumerate();
}
}
bool Enumerate()
{
int sum = 0;
int startIndex = 0;
int endIndex = _elements.size() - 1;
int i;
if (_indexList.size() == 0 || _indexList[0] == _n - _k)
{
return false;
}
for (i = _k - 1; i > 0 && _indexList[i] == _n - _k + i; i--)
{
}
_indexList[i] ++;
for (int j = i; j < _k - 1; j++)
{
_indexList[j + 1] = _indexList[j] + 1;
}
int cacheValue = GetCachePartialSum(i);
for (int calcIndex = 0; calcIndex <= i; calcIndex++)
{
sum += calcSquareSum(startIndex, _indexList[calcIndex]);
startIndex = _indexList[calcIndex];
}
int partialSum = 0;
int squareSum = 0;
if (cacheValue != -1)
{
squareSum = calcSquareSum(startIndex, _indexList[i + 1]);
sum += squareSum;
partialSum = cacheValue;
sum += partialSum;
}
else
{
for (int calcIndex = i + 1; calcIndex < _indexList.size(); calcIndex++)
{
squareSum = calcSquareSum(startIndex, _indexList[calcIndex]);
partialSum += squareSum;
sum += squareSum;
startIndex = _indexList[calcIndex];
}
squareSum = calcSquareSum(startIndex, endIndex + 1);
partialSum += squareSum;
sum += squareSum;
}
_minSum = min(_minSum, sum);
CachePartialSum(partialSum);
if (cacheValue != -1)
{
SkipIndex(i);
}
return true;
}
void SkipIndex(int cachePos)
{
int lastElem = _elements.size() - 1;
for (int i = _indexList.size() - 1; i >= cachePos + 2; i --)
{
_indexList[i] = lastElem;
lastElem--;
}
}
int GetCachePartialSum(int &pos)
{
int cacheValue = -1;
for (int i = _indexList.size() - 1; i >= 0; i--)
{
int value = _cache[i][_indexList[i]];
if (value == -1)
{
break;
}
pos = i - 1;
cacheValue = value;
}
return cacheValue;
}
void CachePartialSum(int partialSum)
{
int lastElem = _elements.size() - 1;
bool firstLoop = true;
for (int i = _indexList.size() - 1; i >= 0; i--)
{
if (firstLoop == true)
{
_cache[i][_indexList[i]] = partialSum;
firstLoop = false;
}
if (_indexList[i] == lastElem)
{
if (i - 1 >= 0)
{
int parentIndex = _indexList[i - 1];
int minPartial = g_INFINITE;
for (int child = parentIndex + 1; child <= lastElem; child++)
{
int cacheValue = _cache[i][child];
int squareSum = calcSquareSum(parentIndex, child);
minPartial = min(minPartial, cacheValue + squareSum);
}
_cache[i - 1][_indexList[i - 1]] = minPartial;
}
}
else
{
break;
}
lastElem--;
}
}
int GetResult()
{
return _minSum;
}
int calcSquareSum(int start, int end)
{
if (start == end - 1 && end == _elements.size())
{
return 0;
}
int &sum = _squareSumCache[start][end];
if (sum == -1)
{
int partialSum = 0;
for (int i = start; i < end; i++)
{
partialSum += _elements[i];
}
int quantizeNumber = round(partialSum / ((double)end - start));
int squareSum = 0;
for (int i = start; i < end; i++)
{
int diff = (_elements[i] - quantizeNumber);
squareSum += (diff * diff);
}
sum = squareSum;
}
return sum;
}
};
// https://algospot.com/judge/problem/read/QUANTIZE
int main()
{
int cases;
cin >> cases;
for (int i = 0; i < cases; i++)
{
int productSequare = 0;
cin >> g_seqCount;
cin >> g_quantizeCount;
set<int> numbers;
memset(g_seq, 0, sizeof(int) * MAX_N);
for (int j = 0; j < g_seqCount; j++)
{
cin >> g_seq[j];
numbers.insert(g_seq[j]);
}
if (numbers.size() <= g_quantizeCount)
{
cout << productSequare << endl;
continue;
}
sort(g_seq, g_seq + g_seqCount);
{
Partition c(g_seq, g_seqCount, g_quantizeCount);
while (c.Enumerate() == true);
cout << c.GetResult() << endl;
}
}
return 0;
}
실제로 위의 코드로 답을 제출하면 24ms 수행 시간으로 algospot 채점을 통과합니다.
물론, 책의 구간 분할로 풀면 8ms로 답이 더 빠르게 나옵니다. ^^ 바람직한 것은 책의 방법이지만 어쨌든 책을 공부하지 않았을 상황에서도 답을 낼 수 있었다는 사실과, 조합으로도 cache 적용을 통해 약간의 부분 문제화할 수 있었던 것에 만족할 수 있겠습니다.
(
첨부 파일은 이 글의 마지막 예제 코드를 포함합니다.)
[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]