👀 'Do it! 알고리즘 코딩테스트 with Python(김종관 저)'을 공부하고 정리한 내용입니다.

1. 누적합(합배열)

누적 합(합 배열)은 기존의 배열을 전처리한 배열입니다. 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는 문제의 시간복잡도가 O(N)에서 O(1)로 감소합니다.

합 배열(누적합) S를 만드는 공식은 다음과 같습니다.
S[i] = s[i-1] + A[i]

2. 구간합

구간 합은 합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 알고리즘입니다. 위에서 다룬 누적합에 대한 이해를 가지고 있다면, 구간합을 계산하는 것은 어렵지 않습니다.

예를들어 배열 A중, i번째와 j번째 사이의 값을 모두 합한 값을 구하고 싶다면,

i번째까지의 누적합에서 i-1번째 까지의 누적합을 빼주면 원하는 구간합을 구할 수 있습니다.