[알고리즘] 누적합 (Prefix Sum)

누적합(Prefix Sum)은 배열 또는 리스트 등에서 일정 구간의 합을 빠르게 계산하기 위한 방법이면서 동적 계획법(DP)의 형태 중 하나이다.

기본적인 방식은 각 요소까지의 누적합을 계산하여 이를 배열에 저장해 두는 것이다. 이후 특정 구간의 합을 구할때 저장해둔 배열을 사용한다.

 

동적계획법(DP, Dynamic Programming)

여기서 동적계획법을 간단히 설명하면 DP, 즉 Dynamic Programming의 줄임말로 기본적인 아이디어는 하나의 큰문제를 여러 개의 작은 문제로 나누어서 해결하고 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다.

DP는 특정한 알고리즘이 아닌 문제해결 패러다임으로 해당 이름은 큰 의미가 없이 지어졌다고 한다.

 

누적합 조건

•  누적합은 배열의 값들이 변하지 않아야 한다.

---

1차원 누적합 

1차원 누적합

1차원 누적합은 해당 인덱스 만큼 누적해서 더해주면된다.

누적합의 0번 인덱스 요소는 배열의 0번 인덱스 요소와 똑같이 해주고

1번 인덱스 부터는 이전 인덱스의 누적합 + 해당 인덱스를 해주면 된다.

 

이를 공식으로 i (i > 0)번 인덱스 누적합을 구하는 공식으로 적으면

prefix_sum[i] = prefix_sum[i-1] + array[i]

가 된다.

 

1차원 누적합 C# 코드

 // 누적합 구하는 코드
int[] array = { 1, 2, 3, 4, 5, 6 };
int n = array.Length;
int[] prefix_sum = new int[n];

prefix_sum[0] = array[0];
for(int i = 1; i < n; i++)
{
    prefix_sum[i] = prefix_sum[i-1] + array[i];
}


foreach(int i in prefix_sum)
{
    Console.Write(i + " "); // 1 3 6 10 15 21
}

 

1차원 누적합

누적합 배열 특정 index를 호출하면 해당 인덱스까지의 누적합을 구할 수 있다.

위 예시에선 prefix_sum[3]을 호출하면 array의 인덱스3 까지의 누적합 10을 바로 구할 수 있게 된다.

 

구간합

구간합은 배열의 특정 구간의 합을 말하는데, 누적합 배열을 이용하면 쉽게 구할 수 있다.

 

구간합의 공식은 인덱스 x, y (x < y)의 구간합을 구한다고 하면

prefix_sum[y] - prefix_sum[x-1] 이 된다.

공통으로 누적합된 부분을 빼준다고 생각하면 된다.

 

누적합을 이용해서 구간합을 구하면 일반적인 for문 계산보다 빠르게 계산할 수 있는데

예를 들어 index 2번 부터 5번까지 더한다고 가정했을때

누적합 없이 for문을 통해 구간합을 구하면 3 + 4 + 5 + 6 으로 O(N) 만큼의 시간이 걸린다.

하지만 누적합을 이용하면 21 - 3으로 O(1) 만큼의 시간이 걸리게 된다.

---

2차원 누적합

2차원 누적합

2차원 배열 누적합은 1차원 배열 보다 좀 더 복잡하다.

 

2차원 누적합

첫 열과 행은 1차원 배열처럼 단순히 누적합 해주면된다.

 

2차원 누적합

첫 열과 행을 제외한 다른 인덱스 들은 단순히 위쪽과 왼쪽의 값만 더하면 안되고 위쪽과 왼쪽의 공통된 누적합을 같이 빼줘야한다.

위 그림처럼 (1, 1)의 누적합을 구한다고 생각하면 1 + 2 + 5 + 6 이기 때문에 14가 나와야한다.

하지만 3 + 6 + 6은 15가 된다. 3과 6의 누적합을 구할때 더해진 1이 중복 됬기 때문이다. 그래서 공통된 누적합을 빼줘야 한다.

 

배열 arr의 (x, y)의 누적합을 구한다고 생각하면,

prefix_sum[x, y] = arr[x, y] + prefix_sum[x-1, y] + prefix_sum[x, y-1] - prefix_sum[x-1, y-1]

라는 공식이 나온다.

 

2차원 누적합

하지만 여기서 0번째 열과 행을 구할때 위 공식을 이용하면 인덱스를 벗어나 Index예외가 발생한다. 이를 방지하기 위해 누적합 배열의 첫열과 행에 0을 추가해준다.

 

그럼 2차원 누적합을 구하는 공식이 arr의 인덱스가 prefix_sum보다 1씩 작아지기 때문에

prefix_sum[x, y] = arr[x-1, y-1] + prefix_sum[x-1, y] + prefix_sum[x, y-1] - prefix_sum[x-1, y-1]

이 된다.

2차원 누적합 C# 코드

// 2차원 누적합 구하는 코드
int[,] matrix = new int[4, 4] { { 1, 2, 3, 4 },
                                { 5, 6, 7, 8 }, 
                                { 9, 10, 11, 12}, 
                                { 13, 14, 15, 16} };
int wSize = matrix.GetLength(0); // 4
int hSize = matrix.GetLength(1); // 4

int[,] prefix_sum = new int[wSize + 1, hSize + 1];
for(int i = 1; i < wSize+1; i++)
{
    for(int j = 1; j < hSize+1; j++)
    {
        prefix_sum[i, j] = matrix[i - 1, j - 1] + prefix_sum[i - 1, j] + prefix_sum[i, j - 1] - prefix_sum[i-1, j-1];
    }
}


for(int i = 0; i < prefix_sum.GetLength(0); i++)
{
    for(int j = 0; j < prefix_sum.GetLength(1); j++)
    {
        Console.Write(prefix_sum[i, j] + " ");
    }
    Console.WriteLine();
}
/*
 0 0 0 0 0
 0 1 3 6 10
 0 6 14 24 36
 0 15 33 54 78
 0 28 60 96 136
 */

 

구간합

2차원 배열도 1차원 배열과 마찬가지로 누적합 구간간의 차이를 구하면 된다.

 

2차원 누적합

위 그림 처럼 (x1, y1)부터 (x2, y2)의 구간합을 구한다고 가정해보자.

1차원 배열 구간합 처럼 공통으로 누적합된 부분을 빼주면 된다.

 

2차원 누적합

위 그림에서 연두색은 공통된 영역임으로 빼주면 된다.

하지만 살구색으로 표시된 영역은 공통된 영역인 연두색 영역을 빼주면서 2번 빠지게 된다.

때문에 해당 영역을 1번 더해주면 구간합을 구할 수 있다.

 

이를 식으로 표현하면

range(x1,y1 ~ x1, y2) = prefix_sum[x2, y2] - prefix_sum[x1 -1, y2] - prefix_sum[x2, y1 -1] + prefix_sum[x1 -1, y1 -1]

이 된다.

// 2차원 누적합 구하는 코드
int[,] matrix = new int[4, 4] { { 1, 2, 3, 4 },
                                { 5, 6, 7, 8 }, 
                                { 9, 10, 11, 12}, 
                                { 13, 14, 15, 16} };
int wSize = matrix.GetLength(0); // 4
int hSize = matrix.GetLength(1); // 4

int[,] prefix_sum = new int[wSize + 1, hSize + 1];
for(int i = 1; i < wSize+1; i++)
{
    for(int j = 1; j < hSize+1; j++)
    {
        prefix_sum[i, j] = matrix[i - 1, j - 1] + prefix_sum[i - 1, j] + prefix_sum[i, j - 1] - prefix_sum[i-1, j-1];
    }
}

// 2차원 배열 구간합
int x1 = 2;
int y1 = 2;
int x2 = 4;
int y2 = 4;

int range = prefix_sum[x2, y2] - prefix_sum[x1 - 1, y2] - prefix_sum[x2, y1 - 1] + prefix_sum[x1 - 1, y1 - 1];

Console.WriteLine(range); // 99

---

관련 코딩테스트 문제

[C#][프로그래머스] 연속 부분 수열 합의 개수

 

---

참고 사이트

https://hongjw1938.tistory.com/47
https://sjh9708.tistory.com/213
https://code-angie.tistory.com/22
https://jih3508.tistory.com/50