[알고리즘] 누적합(부분 배열 합)

 부분 배열의 합을 구하기 위해서 다양한 방법을 사용할 수 있다.

 

 

1차원 누적합

 

다음과 같은 배열이 있다고 하자.

int[] arr = {1,2,3,4,5};

두 번째부터 다섯 번째 원소까지의 합을 구하기 위해서는, for문을 이용해서 직접 구해줄 수 있다.

for(i=1...5) rst+=arr[i]

그런데 만약 arr이 충분히 크다면, dp를 이용하여 누적합을 저장해두고 갖다 쓸 수 있다.

두번째~다섯번째 원소합 = (첫번째~다섯번째 원소 누적합) - (첫번째~첫번째 원소 누적합)

var s5=0, s1=0
for(i=0...4까지) s5+=arr[i]
for(i=0...0까지) s1+=arr[i]
var arr[1]부터 arr[5]까지 합 = s5-s1

일반화하면 다음과 같은 식이 나온다. 따라서 누적합 배열을 만들어둔다면 이 식을 이용해서 O(1)의 시간복잡도로 원소의 합을 구할 수 있다.

arr[i]+...arr[j] = 누적합[j]-누적합[i-1];

 

boj 11659) 구간 합 구하기 4

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line_1 = br.readLine().split(" ");
        String[] line_2 = br.readLine().split(" ");
        int N = Integer.parseInt(line_1[0]);
        int M = Integer.parseInt(line_1[1]);
        int[] arr = new int[N];
        int[] sum = new int[N];

        for(int i=0; i<N; i++) //배열에 값 저장
            arr[i] = Integer.parseInt(line_2[i]);

        sum[0] = arr[0];
        for(int i=1; i<N; i++) { //1~i까지 누적합
            sum[i] = sum[i-1]+arr[i];
        }

        for(int i=0; i<M; i++) {
            String[] range = br.readLine().split(" ");
            int l = Integer.parseInt(range[0]);
            int r = Integer.parseInt(range[1]);
            System.out.println(sum[r-1]-sum[l-1]+arr[l-1]);
            //(==sum[r-1]-sum[l-2])
        }
    }
}

 

 

이를 응용하면 다음과 같은 사고도 할 수 있다.

 

주어진 input으로 배열을 채워나가고, 그 합의 최대값이 되는 부분을 구하는 문제에서 활용 가능하다. 간단하게 말하면 도서관 열람실을 이용하는 사람들의 사용시간들이 주어지고, 가장 많은 사람들이 도서관을 이용하는 시간(혹은 그때 사람 수)을 구한다고 하자. 일반적으로 대충 다음과 같은 풀이가 가장 먼저 떠오를 것이다.

 

int p1start=13, p1end=17; //사람 1의 도서관 이용 시작/종료시간
int p2start=15, p2end=20; //사람 2의 도서관 이용 시작/종료시간

for(int i=p1start; i<=p1end; i++) timetable[i]++;
for(int i=p2start; i<=p2end; i++) timetable[i]++;

for(int i=0; i<=23; i++) ans = max<timetable[i]?i:ans; //가장 사용자가 많은 시각
for(int i=0; i<=23; i++) ans = Math.max(timetable[i]); //가장 사용자가 많은 때의 사람수

 

사람의 도서관 이용시간을 해당 시간에 도서관을 이용하는 사람의 수를 나타내는 배열 timetable에 저장하고, timetable을 탐색하면서 가장 큰 값을 갖는 시간(혹은 그때의 사람 수)을 얻으면 된다. 이러한 풀이는 O(n^2)의 시간복잡도를 가지는데, 누적합을 잘 이용하면 이러한 문제를 O(n)에 해결할 수 있게 된다.

 

int p1start=13, p1end=17; //사람 1의 도서관 이용 시작/종료시간
int p2start=15, p2end=20; //사람 2의 도서관 이용 시작/종료시간

timetable[p1start]++;
timetable[p1end]--;
timetable[p2start]++;
timetable[p2end]--;

for(int i=1; i<timetable.size; i++) timetable[i]+=timetable[i-1];

//구해진 timetable은 위와 동일하게 사용

 

사용자의 시작시간에 해당하는 timetable배열에는 1을 더해주고, 종료시간에 해당하는 timetable에는 1을 빼주는 과정만을 반복한다. 즉, 모든 사용시간을 탐색하면서 값을 수정해주지 않기에 O(n)만에 해결 가능하다. 그후에는 timetable배열을 대상으로 누적합을 구해주면 된다.

 

원리는 간단하다(머리로도 쉽게 이해 가능하다). timetable을 해당 시간에 이용하는 사용자 수로 생각하지 말고, 해당 시간에 들어오는 사용자 수로 생각하면 된다. 그러고 나서 누적합을 구해주면 그 누적합이 해당 시간에 도서관을 이용하는 사용자 수가 되는 것이다.

 

 

프로그래머스) 호텔 대실

https://school.programmers.co.kr/learn/courses/30/lessons/155651

프로그래머스

 

비슷한 문제를 하나 풀어보자. 사용자들의 대실 시간이 주어지고, 해당 사용자들을 모두 수용하기 위해서는 최소 몇개의 방을 필요로 하는가가 문제이다. 필요한 방의 개수를 구하는데 어떤 방법을 써야하는지 고민했는데, 결국 동시에 최대 몇명의 사람이 들어오는지를 구해주면 되는 문제이다. 그런데 이 문제의 경우 이용시간이 분 단위로 주어지므로, 시간을 분 단위로 풀어서 24(시간)*60(분)+10(청소시간)만큼의 배열을 만들고, 그 배열 위에 이용 시작/종료시간을 표시한 다음 누적합을 구해주면 해당 시간의 이용자 명수를 구할 수 있다.

 

import java.util.*;
//배열 누적합
class Solution {
    static final int DAY=60*24+10+1; //하루+청소시간
    static final int HOUR=60;
    static int[] arr = new int[DAY];
    static int ans;
    public int solution(String[][] book_time) {
        for(int t=0; t<book_time.length; t++) {
            int start_h = Integer.parseInt(book_time[t][0].split(":")[0]);
            int start_m = Integer.parseInt(book_time[t][0].split(":")[1]);
            int end_h = Integer.parseInt(book_time[t][1].split(":")[0]);
            int end_m = Integer.parseInt(book_time[t][1].split(":")[1]);
            arr[start_h*HOUR+start_m]++;
            arr[end_h*HOUR+end_m+10]--;
        }
        
        ans = arr[0];
        for(int i=1; i<arr.length; i++) {
            arr[i]+=arr[i-1];
            ans = Math.max(ans, arr[i]);
        }
        
        return ans;
    }

}

 

 

 

2차원 누적합

 

 1차원 배열과 유사하게 2차원에서도 누적합을 사용할 수 있다. 현재 인덱스보다 하나 적은 인덱스까지의 누적합에 현재 배열값을 더해주기만 하면 되는 일차원 배열 누적합의 초기화와 다르게, 2차원 배열은 누적합을 사용하기 위한 dp값을 다음과 같이 초기화한다.

- s[i][j]: arr[0][0]부터 arr[i][j]까지의 인덱스 값의 합
- 초기화) s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + arr[i][j]
- 점화식) arr[i1][j1] ~ arr[i2][j2]까지의 인덱스값 합
= s[i2][j2] - s[i2][j1-1] - s[i1-1][j2] + arr[i1-1][j1-1]

 

추가로 누적합 2차원문제를 풀때는 (n+1)*(m+1)크기로 배열을 짜도록 하자. idx-1을 조회하는 부분이 많아서 n*m으로 짤 시 분기를 두어 풀어야한다.

 

 

웰노운, 추가 예정) 누적합 활용

https://school.programmers.co.kr/learn/courses/30/lessons/92344