[알고리즘] 구간 합, 누적 합

코드보다는 알고리즘 접근 방법에 대해 정리합니다!

 

1. 누적 합이란?

배열에서 0번째 인덱스부터 N번째 인덱스까지 탐색을 진행하면서 누적해서 값을 더한 결과를 말합니다.

array[1,3,5,6,7,9,13]가 있으면 1부터 13까지 순차적으로 탐색하면서 값을 더한 것을 말하는데, 다만 값을 단순하게 더하는 것이 아닌 누적해서 더한다는 것이 포인트입니다.

1+, (1+3), (1+3+5), (1+3+5+6), ... 이런식으로 더해 나가야하는 거죠!

코드로 단순하게 구현해 보면 아래와 같은 모습이 됩니다.

for(int i = 0; i<n; i++){
	for(int j = 0; j<=i; j++){
    	sum[i] += arr[j];
    }
}

이렇게 될 경우 시간 복잡도는 O(N^2)가 걸리게 되는데, sum_arr라는 새로운 배열을 만들고 계산한 값을 배열에 저장해서 사용하면 O(N)으로 누적합을 구할 수가 있게 됩니다!

 

for(int i= 0; i<n; i++){
	sum_arr[i+1] = sum_arr[i] + arr[i];
}
console.log(sum_arr[arr.length])

 

누적이라는 단어가 나온다면, 위처럼 계산한 값을 저장할 새로운 배열을 만들어야겠다는 생각으로 접근하는 것이 좋습니다.

 

 

2. 구간합이란?

누적합의 알고리즘과 같은데, 인덱스만 조금 달라집니다.

 

구간합 알고리즘은 현재 진행 단계의 인덱스까지의 합을 저장하는 sum[] 배열을 사용합니다.

sum[i-1]까지의 총합에 arr[i]를 더하면 sum[i]를 구할 수가 있게 됩니다. 

하지만, 0번째부터 N까지를 구할때 i-1이라는 로직이 들어가기 때문에 sum[]배열을 사용할 경우 arr[]보다 +1 크게 만들고, 초기 값을 0으로 지정해주어야 합니다!