8.9 문제 : Quantization(Python)

문제 출처 : algospot.com :: QUANTIZE

algospot.com :: QUANTIZE

---

1. 문제 분석

(1) 기존의 재귀적인 해법을 찾을 수 있는가?

• 주어진 수열의 첫 번째 숫자를 어떤 숫자로 표현할지 결정하고, 나머지 수열에 대해 재귀 호출로 문제를 해결할 수 있을까?
• 이 문제에서는 양자화 표현으로 사용할 수 있는 숫자의 가짓수에 제한이 있기 때문에 지금까지 사용한 양자화 표현에 사용된 숫자를 무시할 수 없다.
• 이미 s가지의 숫자를 다 쓴 상태라면 s개 중 하나의 숫자를 다시 선택해야 한다.
• 이러한 문제 때문에 최적 부분 구조가 성립하지 않는다.

 

• 남은 숫자들 뿐만 아니라 이전 숫자들을 어떤 숫자로 양자화 했는지 알아야 하기 때문에 지금까지 사용한 숫자들의 집합 역시 입력 받아야 한다.
• 그러나 이러한 완전 탐색은 실로 엄청난 수의 경우를 탐색해야 되고 메모이제이션에 필요한 메모리 역시 확보할 수 없다.

(2) 답의 형태를 제한

• 이러한 경우와 같이 부분 문제의 개수가 너무 많을 때 유용하게 쓰이는 방법 중 한 가지는 바로 답이 항상 어떤 구조를 가질 것이라고 예측하고 그것을 강제하는 것이다.
• 이 문제에 적용해보자면 a < b인 두 수에 대해서 a를 양자한 값 a'가 b를 양자화한 값 b'보다는 커서는 안된다.(1을 7로 양자화 했는데 9를 6으로 양자화 하면 절대로 최적해가 나올 수 없다...)
• 이를 일반화 하면 '주어진 수열을 정렬하면, 같은 숫자로 양자화 되는 숫자들은 항상 인접해 있다.' 라고 강제할 수 있다.
• 최종적으로 구해야 하는 오차 제곱의 합은 수열의 순서가 바뀌더라도 상관 없기 때문에 가능하다.

 

• 따라서, 이 문제는 주어진 수열을 s개의 묶음으로 나누는 문제가 된다.
• 매번의 재귀 호출마다 첫 묶음의 크기가 얼마일지를 결정하면 된다.
• 정렬된 수열의 n개의 숫자들 중 첫 묶음의 크기를 x라고 한다면 이제 n-x개의 숫자들을 s-1개의 묶음으로 나누면 된다!
• 또한, 남은 s-1 묶음의 오차 제곱의 합이 최소여야 전체도 최소이기 때문에 최적 부분 구조 역시 성립한다.

 

• quantize(from, parts) : from번째 이후의 숫자들을 parts개의 묶음으로 묶을 때 최소 오류 제곱의 합을 반환
• minError(a, b) : a번째 숫자부터 b번째 숫자까지를 하나의 수로 양자화 했을 때의 최소 오류 제곱의 값을 반환
• 첫 묶음의 크기가 size일 때, 최소 오류는 다음과 같다.
• minError(From, from + size - 1) + quantize(from + size, parts - 1)

 

• 이를 점화식으로 표현하면 size가 1부터 n-from일 때,
• quantize(from, parts) = min(minError(from, from + size - 1) + quantize(from + size, parts - 1))

(3) minError(a, b) 구현하기

• minError의 동작 과정은 크게 2가지이다.
• 1. 주어진 구간을 어떤 수로 표현(양자화)할지 결정
• 2. 결정한 수 m으로 해당 구간을 표현했을 때 오차를 계산하기

 

• 간단하고 직관적인 방법으로는 a부터 b사이의(수열을 정렬했으므로 항상 a<b일 것이다.) 모든 수에 대해서 해당 구간의 최소 오차 제곱을 구하는 방법이다.
• 그러나 미분을 이용하면 한 번에 m을 알아낼 수 있다.

 

• 먼저, 임의로 결정한 m에 대해서 수열 A의 A[a]부터 A[b]까지의 모든 수에 대한 최소 오차 제곱을 구하는 수식은 다음과 같다.

• 이를 m에 대한 이차 함수 y로 간주하고 y를 m에 대해 미분한다.

• 최고차항이 양의 계수인 이차 함수 y가 최솟값을 갖는 경우는 바로 미분한 값이 0이 되는 부분이다. 따라서 위의 미분한 수식에서 0이 되는 m을 찾으면 된다.

• 따라서, m이 위의 값을 가질 때 최소 오차 제곱을 갖는 것을 알 수 있다.
• 그런데 이 값은 a부터 b까지의 합을 a와 b의 개수로 나눈 즉, 주어진 구간에서의 평균값을 의미한다!
• 문제에서는 양자화 표현에 정수만을 사용할 수 있으므로 평균에 가장 근접한 정수값을 m으로 사용하기로 한다.

 

• 일반적으로 주어진 구간의 평균을 계산하는 작업은 O(n)의 시간이 소요된다.
• 추후 17장에서 배울 부분 합 기법을 이용해 O(1) 시간에 a부터 b까지 구간의 합을 계산할 수 있다.(단, a는 1이상)

• pSum[b]-pSum[a-1]를 b-a+1로 나누면 m을 상수 시간에 구할 수 있다.
• 단, pSum[b]과 pSum[a-1]이 사전에 미리 계산되어 있어야 한다.
• 최소 오차 제곱을 곱할 때는 m과 관련이 없기 때문에 A[i]^2 역시 상수 시간에 구할 수 있다.
• 알고리즘의 전체 시간 복잡도는 부분 문제의 수 O(ns)에 각 부분 문제의 답을 계산하는데 드는 시간 O(n)을 곱한 O(n^2*s)가 된다.

---

2. 코드 구현(해설 풀이 방법)

(1) precalc() : 부분 합 구하기

INF = int(10e9) # 무한대의 값을 의미하는 전역변수

# array를 정렬하고 각 부분합을 계산
# pSum[] : array[]의 부분합을 저장 (pSum[i]는 array[0] ~ array[i]의 합)
# pSqSum[] : array[]의 제곱의 부분합을 저장 (pSqSum[i]는 array[0]^2 ~ array[i]^2의 합)
def precalc():
    array.sort()
    pSum[0] = array[0]
    pSqSum[0] = array[0] * array[0]

    for i in range(1, n):
        pSum[i] = pSum[i-1] + array[i]
        pSqSum[i] = pSqSum[i-1] + array[i] * array[i]

• m을 상수 시간에 계산하기 위해 사전에 부분 합을 먼저 계산한다.

(2) minError(low, high) : low부터 high까지의 최소 오차 제곱을 계산

# array[low] ~ array[high] 구간을 하나의 숫자로 표현할 때 최소 오차 합을 계산
def minError(low, high):
    # 부분합을 이용하여 A[low]부터 A[high]까지의 합을 구함
    low_value = 0 if low == 0 else pSum[low-1]
    sum_value = pSum[high] - low_value

    sq_low_value = 0 if low == 0 else pSqSum[low-1]
    sq_sum_vlaue = pSqSum[high] - sq_low_value

    # 이 합의 평균을 반올림한 값으로 양자화 표현
    m = int(0.5 + sum_value / (high - low + 1))

    # sum(A[i]-m)^2을 전개한 결과를 부분 합으로 표현
    result = sq_sum_vlaue - 2 * m * sum_value + m * m * (high - low + 1)
    return result

• 문제 분석 단계에서 a부터 b구간에 대한 부분합을 구할 때 a(=low)는 1이상임을 가정 했으므로 a=0은 예외 처리한다.
• 양자화되는 값은 정수이므로 구간의 평균을 반올림해서 나오는 정수를 m으로 결정
• 최소 오차 제곱을 반환하는데 문제 분석 단계에서 수식으로 전개한 것을 코드로 옮긴 것이다.

(3) quantize(from, parts)

def quantize(from_index, parts):
    # 기저 사례 1 : 모든 숫자를 양자화한 경우
    if from_index == n:
        return 0

    # 기저 사례 2 : 숫자는 아직 남아있는데 더 묶을 수 없어 아주 큰 값을 반환
    if parts == 0:
        return INF

    if cache[from_index][parts] != -1:
        return cache[from_index][parts]

    cache[from_index][parts] = INF
    
    # 조각의 길이를 변화시키며 최소치를 찾음
    partSize = 1
    while (from_index + partSize <= n):
        cache[from_index][parts] = min(cache[from_index][parts], minError(from_index, from_index + partSize - 1) + \
            quantize(from_index + partSize, parts - 1))
        partSize += 1

    return cache[from_index][parts]

(4) 문제 입-출력

for tc in range(int(input())):
    n, s = map(int, input().split())

    cache = [[-1] * 11 for _ in range(101)]
    pSum = [0] * 101
    pSqSum = [0] * 101

    array = list(map(int, input().split()))
    precalc()
    print(quantize(0, s))

• cache에 저장되는 값들은 cache[n][s]의 형태(수열의 길이가 n이고 표현할 숫자의 수 s개일 때 최소 오차 제곱의 합을 저장)이므로 각각 n의 최댓값인 100과 s의 최대값 10에 1씩 더해준 101개의 행, 11개의 열을 가진 이차원 리스트로 저장 공간 생성
• 부분 합을 저장하는 pSum과 pSqSum에도 마찬가지로 최대 수열의 길이 100에 대해 +1을 해준 101개의 원소를 저장하는 리스트로 저장 공간 생성

 

---

3. 후기

  난이도가 중인 만큼 설계 단계가 매우 복잡했던 문제였다. 사실 처음 책을 읽고 문제를 풀 때는 과정을 상당수 이해하지 못 했었는데 블로그에 포스팅하면서 다시 천천히 읽어보니 이제 이해가 가기 시작했다. 일반적인 완전 탐색으로는 최적 부분 구조가 나오지 않는데 이를 조금 변형하니(수열을 정렬) 최적 부분 구조가 성립되는 것을 확인할 수 있는 의미있는 문제라고 생각이 든다.

  마지막으로 미분 공부했을 때가 6년정도 된거 같은데 아직 어느정도 개념을 까먹지 않아서 천만 다행이었다. 아마 까먹었었으면 미분까지 다시 훑어보느라 죽을뻔했을 거 같다. 그 외에도 부분 합 부분은 굉장히 신박했는데 수의 합을 상수 시간에 계산할 수 있는 처음 보는 방법이라 그랬던 것 같다. 조금 웃픈점은 역시 빠른 시간안에 해결할 수 있는 만큼 공간을 많이 잡아먹는걸 보면 시간 복잡도와 공간 복잡도의 관계는 제로섬인 듯 하다.

---

github : Algorithmic_Problem_Soving_Strategies/q4_0.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies