[ Do it! 알고리즘 코딩테스트 with JAVA ] - 구간합

[부분 합 (Partial sum)]

: 부분 합이란 구간 합과 달리 처음부터 특정 인덱스까지의 합을 의미한다 (Array[i] 부터 Array[j]까지의 합)

 

 

 

[구간 합(Prefix sum)]

-> 합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘

보통 1차원 배열에서 i~k 인덱스 사이의 값들의 합을 구하는데 사용한다

(코딩테스트에서 사용 빈도가 높으니 꼭 알아두어야 한다!)

 

- 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다!

 

 

[합 배열 S의 정의]

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

 

합 배열은 기존의 배열을 전처리한 배열이라고 생각하면 된다. 

이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다

 

예를 들어서,  S(t)  = 배열A의 A[0] + A[1] + A[2] + A[3] + A[4] 의 값이다.

 

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[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]

 

 

 

 

 

https://velog.io/@leeeeeyeon/%EA%B5%AC%EA%B0%84-%ED%95%A9-%EB%B6%80%EB%B6%84-%ED%95%A9-%EB%88%84%EC%A0%81-%ED%95%A9

구간 합, 부분 합, 누적 합