알고리즘 스터디 Week2

부분합

0번째 원소부터 i번째 원소까지 더한 값을 저장한 배열

$$psum[i] = \sum_{j=0}^{i} elements[j]$$

 

$elements$ 배열의 크기 $n$에 대해서 $O(n)$의 수행시간으로 계산이 가능하다. (밑의 식을 n번 반복하면 된다)

$$psum[i+1] = psum[i] + elements[i+1]$$

 

부분합 배열 $psum$을 통해 $\sum_{i=a}^{b} elements[i]$를 O(1)로 계산할 수 있다.

$$\sum_{i=a}^{b} elements[i] = psum[b] - psum[i-1]$$

 

이 특징들을 통해, 반복적으로 원소의 범위합에 접근하는 문제에서 부분합을 활용하면 매우 시간을 절약할 수 있다.

$elements$의 크기 n, 원소의 범위합 접근 m번

범위합없이 $elements$ 배열에서 하나씩 접근하였을 때는 원소의 범위합 수행시간 O(n) * m = O(n * m)의 수행시간이고, 범위합을 사용할 시 부분합 준비 O(n), 범위합 계산 O(1) * m = O(m) 총 O(n + m)의 수행시간이 필요하다.

 

범위합과 같은 원리로 범위의 평균도 같은 시간복잡도로 계산된다.

$$average_{a,b} = (psum[b] - psum[a-1]) / (b - a + 1) => O(1)$$

 

범위의 분산

범위의 분산 $v_{a,b}$도 O(1)의 시간복잡도로 계산할 수 있는데,

$$ \begin{align*} v_{a, b}& = {1 \over {b - a + 1}} \sum_{i=a}^b(elements[i] - average_{a, b})^2 \\ & = {1 \over {b - a + 1}} \sum_{i=a}^b(elements[i]^2 -2 \cdot elements[i] \cdot average_{a,b} + average_{a, b}^2)\\ & = {1 \over {b - a + 1}}(  \sum_{i=a}^b(elements[i]^2) -2 \sum_{i=a}^b elements[i] \cdot average_{a,b} + (b - a + 1) \cdot average_{a, b}^2 ) \\ & = {1 \over {b - a + 1}} \{ \sum_{i=a}^b(elements[i]^2) -2 \cdot (psum[b] - psum[a-1])) \cdot \sum_{i=a}^b elements[i] + {1 \over {b - a + 1}} \cdot (psum[b] - psum[a-1])^2 \} \end{align*}  $$

 

여기서 2번째 항과 3번째 항은 O(1)의 시간으로 구할 수 있으며, 1번째 항의 경우 $psum$을 계산하는 부분에 $sqpsum$을 추가하면 된다.

$$sqpsum[i] = \sum_{j=0}^{i} elements[j]^2$$

 

2차원에서의 부분합

(0, 0)과 (x, y) 직사각형을 만들어 그에 해당하는 합을 부분합으로 하면 다음과 같다.

$$psum[y, x] = \sum_{i=0}^y \sum_{j=0}^x A[i, j]$$

 

이 때, $(x_1, y_1)$과 $(x_2, y_2)$의 직사각형의 범위합을 구하면 다음과 같이 계산할 수 있다.

$$sum(y_1, x_1, y_2, x_2) = psum[y_2, x_2] - psum[y_2, x_1 - 1] -  psum[y_1 - 1, x_2] + psum[y_1 - 1, x_1 - 1] $$

 

예제

구간합이 0에 가깝다는 것은 부분합1과 부분합2의 차이가 0에 가깝다는 것을 의미한다.

0에 가장 가까운 구간합을 찾으려면, n개의 부분합을 정렬하고 인접한 값의 최소 차이를 구하고 그 두 부분합의 index들을 출력하면 된다. (std::map을 이용하면 key와 value의 std::pair로 접근할 수 있다)

 

 

 

DP 때 풀기!!

https://www.acmicpc.net/problem/2098