[알고리즘(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 ]를 참고해 작성하였습니다.