누적합(Cumulative sum)

누적합의 필요성

알고리즘 문제에서 배열의 부분합을 빠르게 구해야 하는 경우에 누적합을 이용하면 연속된 누적합을 O(N)만에 구할 수 있다.

 

 

누적합의 성질

1. S(n) = 배열 a의 1번째 요소 부터 n번째 요소까지의 누적합
2. S(1) = a(1)
3. S(i) = S(i-1) + a(i)
4. a(i) + a(i+1) + ... + a(j-1) + a(j) = S(j) - S(i-1) // 누적합을 활용한 빠른 구간합 계산

 

1차원 누적합

누적합의 4번 성질을 이용하여 아래 문제들을 해결할 수 있다.

 

1. 구간 합 구하기 4

https://www.acmicpc.net/problem/11659

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int T, n, m, answer;
    static int[] arr, sumArr;
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        init();
        
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<n; i++) {
            arr[i] = stoi(st.nextToken());
            sumArr[i+1] = sumArr[i] + arr[i];
        }
        
        while(m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int start, end;
            start = stoi(st.nextToken());
            end = stoi(st.nextToken());
            
            // s(end) - s(start-1);
            System.out.println(sumArr[end] - sumArr[start-1]);
        }
 
    }
 
    static void init() {
        arr = new int[n];
        sumArr = new int[n+1];
    }
 
    static int stoi(String s) {
        return Integer.parseInt(s);
    }
}
}

 

 

2. 록 페스티벌

https://algospot.com/judge/problem/read/FESTIVAL#

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int T, n, l;
    static double min;
    static int[] arr, sumArr;
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = stoi(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            n = stoi(st.nextToken());
            l = stoi(st.nextToken());
            init();
 
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                arr[i] = stoi(st.nextToken());
                sumArr[i + 1] = sumArr[i] + arr[i];
            }
 
            min = Integer.MAX_VALUE;
            
            for(int start = 0; start<= n-l; start++) {
                for(int end = start+l; end <=n; end++) {
                    double avg = (double)(sumArr[end] - sumArr[start]) / (end-start);
                    min = Math.min(min, avg);
                }
            }
            System.out.println("#" + tc + " " + min);
        }
    }
 
    static void init() {
        arr = new int[n];
        sumArr = new int[n + 1];
    }
 
    static int stoi(String s) {
        return Integer.parseInt(s);
    }
}

 

 

참고 자료

- https://eine.tistory.com/entry/2%EC%B0%A8%EC%9B%90-%EB%88%84%EC%A0%81%ED%95%A9-%EB%B6%80%EB%B6%84%ED%95%A9-%EA%B5%AC%ED%95%98%EA%B8%B0