03. 동적계획법 - 예제3

[1. 문제 설명]

수열을 s 가지의 자연수만을 이용하여 양자화 하였을 때,

각 숫자별 오차 제곱의 합을 최소 값을 출력한다.

 

양자화 => 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현

[161, 164, 178, 184] => 160, 170, 180 으로 표현..

 

 

 

[2. 풀이 접근]

A. 잘못된 접근

주어진 수열 A 이 첫번째 수자를 어떤 숫자로 표현할 것인지 결정하고

나머지 수열에 대해 재귀 호출하는 방식

=> 양자화에 사용 할 숫자에 제한이 있어서, 현재 까지의 결정이 앞으로의 결정에 영향을 준다

=> 최적 부분 조건이 성립하지 않는다.

=> 메모이제이션에 필요한 메모리 확보도 어려울 것.

==> 입력 상, 1000 이하의 숫자 중 10 개의 숫자를 선택하는 경우를 고려해보면...

 

 

B. 올바른 접근

B.1 답의 형태 제한하기

부분 문제의 개수가 너무 많을 때, 시도 할 수 있는 방법

답이 항상 어떤 구조를 가질 것이라고 예측하고, 그것을 강제한다.

 

=> 어떤 숫자 a 와 b 에 대해서 a < b 인 경우

=> a 를 a` 로 양자화 할 때, a` 는 b에 대응되는 값 보다 커서는 안된다.

==> ex) a=10, b=25 이고, b 에 양자값을 20 으로 할 때,

       a 의 양자값이 20보다 커지면, 20 미만일 때 보다 그 오차가 더 커진다.

 

주어진 수열을 오름차순으로 정렬하면,

같은 숫자로 양자화 되는 숫자들은 항상 인접해 있다.

 

따라서, 수열을 정렬하고, 인접한 숫자끼리 묶음으로 적절히 분할하고, 각 묶음을 한 숫자로 양자화 하여,

오차 제곱의 합을 최소화 하는지 확인하도록 한다.

 

즉, 주어진 수열을 s 개의 묶음으로 나누어야 한다.

매 재귀 호출 때마다, 첫 묶음의 크기가 얼마인지 결정하면 된다.

ex) 첫 묶음의 크기가 x 이면, n-x 개의 숫자를 s-1 개의 묶음으로 나누면 된다.

 

이제 최적 부분 구조가 성립하게 된다.

(부분의 오류가 최소이어야, 전체의 오류가 최소가 되기 때문이다.)

(남은 숫자들을 최적으로 묶는데, 이전 조각의 정보는 필요가 없다.)

 

 

B.2 한 구간에 대한 답 찾기

한 구간의 최소 오차 제곱 합을 찾는 가장 쉬운 방법은

주어진 구간의 최소값에서 최대값까지 값 중 하나로 양자화 하여 일일히 계산해보는 것이다.

=> 숫자의 범위가 1000 이하이므로, 시간 내 가능 할 것?

 

그러나, 미분을 이용하여 오차 제곱 합을 최소로 하는 양자 값을 추정 할 수 이다.

이 값을 미지수로 설정하고, 오차 제곱 합 수식의 최소 값을 찾으면 된다.

 

식을 계산하면, 전체 값들의 평균 일 때, 최소가 되는 것을 알 수 있다.

 

한 구간의 범위는 다양 할 수 있으므로, 부분 합을 이용하여 평균을 계산하면,

O(n) 이 아니라 O(1) 의 복잡도로 계산 할 수 있다.

 

 

[3. 코드]