[알고리즘] 구간 합 알고리즘

구간 합 알고리즘

 

 

합 배열 S 정의

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

 

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

 

합 배열 S를 만드는 공식

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

 

i에서 j까지 구간 합을 구하는 공식

S[j] - S[i-1]

 

합 배열과 구간 합 공식을 잘 사용하면 코딩 테스트에서 시간 복잡도를 줄이는 데 많은 도움이 된다.