[알고리즘(Algorithm)] 4. 구간 합(Prefix Sum)

 

 

※ 구간 합(Prefix Sum)

 

구간 합은 합 배열을 이용하여 시간 복잡도(Time complexity)를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘.

즉, 이는 수들의 나열에서 특정 구간의 합을 의미한다. 

 

ex> i~k 인덱스 사이의 값들의 합

 

 

 

* 부분 합(Partial Sum)

처음부터 특정 인덱스까지의 합을 의미한다. 

 

ex> 0~k 인덱스 사이의 값들의 합

 

 

 

 

---

 

 

※ 구간 합의 핵심 이론 (합 배열)

 

배열 A가 있는 경우, 합 배열 S는 다음과 같습니다. 

S[ i ] = A [0] + A[1] + A[2] + ... + A[ i-1 ] + A[ i ]                 // A[0] ~ A[ i ]까지의 합

즉,  합 배열은 기존의 배열을 전처리(Data Preprocessing)한 배열이라 생각할 수 있다.
이처럼 합 배열을 미리 구해놓은 경우, 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서  O(1)로 감소된다. 

합 배열 S[4]=48, S[2]=38 ...

ⓛ  A[ i ]부터 A[ j ]까지의 배열 합을 합 배열 없이 구하는 경우, 
최악의 경우는 i가 0이고 j가 N인 (끝과 끝) 경우로 시간 복잡도는 O(N)이다. 

②  이런 경우, 앞에서 알아본 합 배열을 사용하면, O(1) 안에 답을 구할 수 있다.

---

※ 합 배열 S를 만드는 공식

S[ i ] = S[ i - 1 ] + A[ i ]

 

 

 

---

 

 

※ 구간 합을 구하는 공식

 

S[ j ] - S[ i - 1 ]

* 합 배열을 구한 상태에서, i ~ j 까지의 구간 합을 구하는 공식은 위와 같다.

 

 

구간 합 공식 유도

위 그림은 배열 A에서 A[2] ~ A[5]까지의 구간 합을 합 배열을 통해 구하는 과정이다.

( 파란색 화살표가 구하고자 하는 구간 합 영역 )

 

합 배열을 미리 구하고, 구간 합을 확인하여 보면이가 연관되어 있음을 확인할 수 있다.

A[0] + ... + A[5] (S[5]) 에서

A[0] + A[1] (S[1]) 을 뺴면,

구간 합 A[2] + ... + A[5] 가 나오게 되므로, 구간 합을 구하는 공식 S[ j ] - S[ i-1 ]이 성립되는 것을 확인할 수 있다.

( S[5] - S[2-1] = S[5] - S[1] )

 

 

 

 

* A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정

S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]

S[1] = A[0] + A[1]

S[5] - S[1] = A[2] + A[3] + A[4] + A[5]

 

 

이처럼, 합 배열과 구간 합 공식을 알맞게 사용한다면 시간 복잡도를 줄이는 데 큰 도움이 될 수 있다.

 

 

 

 

 

* 해당 포스팅은 Infrean의 [ 하루코딩 - Do it! 알고리즘 코딩테스트 with java ]를 참고해 작성하였습니다.