Quantization

NOTE

블로그라기 보다는 생각나는 생각나는 대로 두서없이 적는 낙서장이라고 보면 될것 같다.

2019년 4월 11일 20:05~21:50

문제

1. 수열의 길이, 양자화에 쓸 수의 개수, 그리고 수열이 주어졌을 때
2. 최소가 되는 오차 제곱의 합을 리턴하라.
3. 오차 제곱은 실제 값을 R, 양자화 한 값을 Q라할 때, 다음과 같다.\((R-Q)^2\)

Input: 5, 2, [1,2,3,4,5]
Output: 2
//만약 위 수열을 [2,2,3,3,3]으로 양자화 하면, 각각의 오차 제곱은
//[(1-2)^2,(2-2)^2,(3-3)^2,(4-3)^2,(5-3)^2] = [1,0,0,1,4]로 이의 합은 6이다.
//만약 다른 수로 양자화 하여 [2,2,2,4,4]로 양자화 하면, 오차 제곱은
//[1,0,1,0,1]로 이의 합은 3이다.

Input: 10, 3, [3,3,3,1,2,3,2,2,2,1]
Output: 0

Input: 9, 3, [1,744,755,4,897,902,890,6,777]
Output: 651

생각 흐름 - 무식하게 풀기

1. 문제로 주어진 수열의 순서는 별 의미 없다.
2. 정렬해서 두 번째로 주어진 수 만큼 그룹으로 나누고, 각 그룹의 평균값으로 양자화하면 오차가 최소화될 것으로 예상된다.
3. 정렬된 수열에서 그룹 및 평균을 구하는 것을 DP로 해야할 것 같다.
4. DP를 할 때, 재귀 함수 내에서 양자화가 같은 수로 지속 되는 경우와 새로 양자화가 시작되는 두 경우로 분기를 쳐서 두 경우의 최소 오차 제곱을 구하면 될듯?

2019년 4월 12일 19:30~20:40

1. 음… 책의 풀이를 봤는데, 나는 아직 멀었군;; DP를 하는 방식이 잘못됐었어….
2. 정렬하고, 구간의 평균으로 양자화 하는 근거가 책에 설명이 돼있네
3. 부분합을 구하는 방법은 알고 있었는데, 오차 제곱을 $O(1)$에 구할 수 있는지는 몰랐네.
4. 코드에서 DP부분만 고쳐서 했는데, 내 코드랑 결과가 같네… 왜 안돌아가지 ㅡㅡ;;