문제 풀이
직관적인 접근
양자화란 넓은 범위로 이루어진 자료를 더 좁은 범위로 표현하는 것이다. 문제의 양자화는 수열의 수 종류를 요구하는 범위까지 좁히는 것이다. 이 때 좁히는 조건은 각 수의 오차 제곱의 합이 최소가 되어야한다.
이 문제는 앞의 선택이 뒤의 선택에 계속해서 영향을 미치므로, 직관적으로 최적 부분 구조를 설계하는것이 쉽지 않다. 나머지 숫자들을 양자화 하기 위한 숫자 뿐만 아니라, 이전 숫자들을 어떻게 양자화 했는지도 알아야하기 때문이다. 숫자 하나 하나 별로 선택을 인수로 전달하게 되면 그 수가 10개의 숫자 중 1000번 뽑는 경우의 수가 되어 너무 큰 수가 되어 버린다.최적 부분 구조 설계를 위한 문제 축소
그래서 이 문제를 해결하기 위해서는 반드시 문제를 단순화 해야 한다. 쉽게 떠올릴 수 있는 방법은 문제의 수열을 정렬하는 것이다. 문제의 수열을 정렬하게 되면, 같은 숫자로 양자화되는 숫자들이 인접하게 되어 숫자의 구획을 나눌 수 있게 된다.
주어진 수열을 정렬함으로서 각 수에 대해 양자화를 해줘야 했던 문제가 문제가 주어진 숫자의 종류만큼만 양자화를 해야 하는 문제로 대폭 축소 되었다.
이제 문제의 최적 부분 구조를 설계해보면, 한 구획을 양자화 하면 나머지 부분은 최소 구획의 크기인 1부터 최대 구획의 크기인 n-이전 구획 크기까지 구획의 크기를 늘려 나가면서 오차 합을 최소화 할 수 있는 구획의 크기를 찾는 것이다. 이 경우 이전에 만들어진 구획은 문제의 크기를 줄일 뿐 어떤 선택을 했는지는 이후 문제에서 알 필요가 없기 때문에 최적 부분 구조가 성립하게 되는 것이다.
부분합
배열의 평균을 상수 시간에 계산할 수 있음, 추가 학습 필요
