누적합 - 구간 내 숫자의 합을 빠르게 구할때 어떻게 해야하는가?

안녕하세요? 우기의 정신나간 취준일기입니다. 

 

먼저 누적합에 대해서 설명해보겠습니다

 

[3, 6,2 ,6 ,7 ,7 ,2]와 같이 숫자들이 주어졌을때

다음 구간 내 숫자들의 합을 구하는 프로그램을 작성해야한다고 가정합시다.

 

[2 ,5]

[3, 6]

[1, 7]

 

무작정 코드를 작성해야한다고 한다면, 구간이 주어질 때마다 구간 내의 숫자들을 전부 순회하며 합을 구해야합니다.

구간의 최대 크기는 N이므로, 질의 갯수가 Q 라면,  시간복잡도는  O(QN)이 됩니다. 

 

이를 어떻게 개선시킬수있을까요? " 미리 1부터 N까지의 합을 구한뒤 해당 구간을 구할수만 있다면?" 이라는 생각을 가져봅시다. 

 

누적합 배열

누적합 배열을 이와 같은 공식을 사용하여 시간복잡도 O(N)에 걸쳐서 만들게 됩니다. 

\누적합이 없을때의 예시를 들어 문제를 해결해보겠습니다. [2, 5] 구간을 구해보겠습니다. 원래같은경우라면 Arr[2]~Arr[5]을 5번을 걸쳐서 더해줘야 값이 나오게됩니다. 즉 최악의 경우는 O(N)이 되는것입니다.  

누적합 배열을 사용한다면 어떻게 될까요? 

개선된 시간복잡도

 

S[5] = Arr[5]+ Arr[4]+ Arr[3]+ Arr[2]+ Arr[1] 

S[1] = Arr[1]

S[5] -S[1] = Arr[5]+ Arr[4]+ Arr[3]+ Arr[2] 이 되기때문에 시간복잡도 O(1)에 문제를 해결할수있습니다. 

 

배열로 해결하기위해선 2가지 방법들이 존재합니다. Sa-1을 해결하기위해선 a-1>=0 이라는 조건입니다. 

 

1. 기본적으로 배열의 크기를 +1을 하여 Arr[0], PrefixSum[0] =0으로 고정시킨다.

 

2.PrefixSum[N,0] =PrefiSum[N] - PrefixSum[0] + Arr[0]을하여 음수 인덱스를 참조하지않고도 원하는 답을 얻어낼수있음.

 

1번 코드 

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{0, 3, 6, 2, 6, 7, 7, 2};
        int[] prefixSum = new int[8];

        prefixSum[0] = 0;
        for(int i = 1; i <= 7; i++)
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        
        // 구간 [2, 5]까지 합 = 21
        System.out.println(prefixSum[5] - prefixSum[1]);
        // 구간 [1, 5]까지 합 = 24
        System.out.println(prefixSum[5] - prefixSum[0]);
    }
}

 

2번 코드

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 6, 2, 6, 7, 7, 2};
        int[] prefixSum = new int[7];

        prefixSum[0] = arr[0];
        for(int i = 1; i < 7; i++)
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        
        // 구간 [1, 4]까지 합 = 21
        System.out.println(prefixSum[4] - prefixSum[1] + arr[1]);
        // 구간 [0, 4]까지 합 = 24
        System.out.println(prefixSum[4] - prefixSum[0] + arr[0]);
    }
}