Microsoft MVP성태의 닷넷 이야기
기타: 61. algospot.com - 양자화(Quantization) 문제 [링크 복사], [링크+제목 복사]
조회: 9127
글쓴 사람
홈페이지
첨부 파일

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 적용을 통해 약간의 부분 문제화할 수 있었던 것에 만족할 수 있겠습니다.

(첨부 파일은 이 글의 마지막 예제 코드를 포함합니다.)




[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]





[최초 등록일: ]
[최종 수정일: 9/22/2016 ]

Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.
by SeongTae Jeong, mailto:techsharer@outlook.com

비밀번호

댓글 쓴 사람
 



2016-09-23 06시30분
[ryujh] 안녕하세요.
제 생각으로는 동적프로그래밍인 것 같은데(아니면 정정부탁합니다), 동적프로그래밍이 왜 필요한지 느낄 수 있는 설명으로 만족합니다. 책 내용은 일반적이기도 하지만 추상적일 수 있어서 책보고 하기 힘들 수 있는데 설명보니 이해갑니다.

[손님]
2016-09-23 06시41분
맞습니다. ^^ 한창 그 부분을 하고 있습니다.
정성태

... [46]  47  48  49  50  51  52  53  54  55  56  57  58  59  60  ...
NoWriterDateCnt.TitleFile(s)
11086정성태11/1/20165461오류 유형: 366. The Microsoft Passport Container service terminated with the following error: General access denied error
11085정성태10/27/201614228.NET Framework: 615. C# - AForge.NET을 이용한 웹캠 영상 출력 [2]파일 다운로드1
11084정성태10/26/20165587오류 유형: 365. The User Profile Service service failed to the sign-in.
11083정성태10/26/201610421Windows: 131. 윈도우 10에서 사라진 "Adapters and Bindings" 네트워크 우선 순위 조정 기능 [1]
11082정성태10/26/20169475.NET Framework: 614. C# - DateTime.Ticks의 정밀도 [4]파일 다운로드1
11081정성태10/26/20165390오류 유형: 364. You need to fix your Microsoft Account for apps on your other devices to be able to launch apps and continue experiences on this device.
11080정성태10/24/20168632Windows: 130. Windows Server 2016 Nano 서버 설치 방법
11079정성태10/21/20165758Windows: 129. Windows Server 2016 설치 CD에 있는 Convert-WindowsImage.ps1 사용 방법 정리
11078정성태10/21/20167168Windows: 128. Windows Server 2016 Nano 서버 VHD 이미지 만드는 방법 - TP5 기준
11077정성태10/21/20167295오류 유형: 363. Active Directory 서버의 NETLOGON 서비스가 멈췄을 때 발생하는 문제
11076정성태10/21/20165291오류 유형: 362. 윈도우 백업 시 오류 - 0x80780040
11075정성태10/20/20166644Windows: 127. Convert-WindowsImage.ps1 사용 방법 정리
11074정성태10/20/201612034Windows: 126. Windows Server 2016 평가판을 정식 버전으로 라이선스 변경하는 방법
11073정성태1/6/20187981.NET Framework: 613. 윈도우 데스크톱 응용 프로그램(예: Console)에서 알림 메시지(Toast notifications) 띄우기파일 다운로드1
11072정성태10/20/20165943VC++: 102. 새로 추가한 ATL COM 객체가 regsvr32.exe로 등록이 안되는 문제
11071정성태10/20/20167090.NET Framework: 612. UWP(유니버설 윈도우 플랫폼) 앱에서 콜백 함수 내에서의 UI 요소 접근 방법 [1]
11070정성태10/21/20165431Windows: 125. 윈도우 서버 2016 마이그레이션
11069정성태3/25/201710050.NET Framework: 611. C++ 개발자들을 위한 C# Thread 동작 방식 [3]
11068정성태5/24/201910991Windows: 124. 윈도우 운영체제의 시간 함수 (5) - TSC(Time Stamp Counter)와 QueryPerformanceCounter [10]파일 다운로드1
11067정성태2/6/20188989Windows: 123. 윈도우 운영체제의 시간 함수 (4) - RTC, TSC, PM Clock, HPET Timer [2]
11066정성태2/6/20187184Windows: 122. 윈도우 운영체제의 시간 함수 (3) - QueryInterruptTimePrecise, QueryInterruptTime 함수파일 다운로드1
11065정성태2/6/20189636Windows: 121. 윈도우 운영체제의 시간 함수 (2) - Sleep 함수의 동작 방식
11064정성태10/19/20196172.NET Framework: 610. C# - WaitOnAddress Win32 API 사용파일 다운로드1
11063정성태2/6/201815725Windows: 120. 윈도우 운영체제의 시간 함수 (1) - GetTickCount와 timeGetTime의 차이점 [5]파일 다운로드1
11062정성태10/12/20165938오류 유형: 361. WCF .svc 호출 시 Could not find a base address that matches scheme net.tcp 예외
11061정성태10/12/201611395오류 유형: 360. IIS - 500.19 오류 (0x80070021)
... [46]  47  48  49  50  51  52  53  54  55  56  57  58  59  60  ...