Prefix sum ( 누적합 )
장점 : 한번 누적합 배열을 만들어 놓으면 구간합을 빠르게 구할 수 있다.
구간합 : 배열에서 특정 구간의 합 ( 예시 : arr[1234] ~ arr[1000000]까지의 모든 원소들의 합 )
속도차이 ( 시간복잡도 )
반복문을 사용해서 구간합을 연속적으로 구하는 일반적인 경우 시간복잡도는
O(n)(반복문) x O(n)(구간합계산) = O(n²)이다.
하지만 누적합을 사용한다면
O(n)(누적합 배열 구현) + O(n)(반복문) x O(1)(구간합 계산) = O(n)이 된다.
즉 훨씬 빠르다는 소리다.
구현예시
누적합 구현시, 현재 위치 직전의 인덱스를 사용하기 때문에 기존 배열의 0번째 인덱스는 비워두는 편이 구현하기 수월하다.
아래 코드와 그림을 보면 더 쉽게 이해할 수 있다.
// 주어진 배열 (0번째 인덱스가 비워진 상태)
int[] a = new int[]{0,10,20,30,40,50,60,70,80,90,100};
// 누적합 배열 구현
int[] prefixSum = new int[a.length];
for(int i = 1 ; i< a.length ; i++){
// 현재 위치 직전 인덱스(i-1) 사용
prefixSum[i] = prefixSum[i-1] + a[i];
}
// 기존배열 a의 구간(6~10)의 구간합 계산
System.out.println( prefixSum[10] - prefixSum[5] );
참고자료
( 부족한 부분이나 수정해야 할 부분을 알려주시면 매우 압도적으로 감사하겠습니다! )
