알고리즘 ] 부분합, 누적합(Prefix Sum)

 

 

  Prefix Sum은 나열된 수의 누적된 합을 말합니다. N개의 원소로 이루어진 배열이 주어졌을때 반복문을 이용해 부분 배열의 합을 구하려면 O(N)의 시간복잡도를 가집니다. 부분합을 이용하면 모든 부분합을 O(1)으로 구할 수 있습니다.

 

 

본 포스팅은 다음 순으로 작성되었습니다.

1.  1차원 배열
2.  2차원 배열

 

1.  1차원 배열

---

  우선 주어진 배열을 순차 탐색하면서 sum 배열을 만들어주면 됩니다.

인덱스	0	1	2	3	4	5
arr	3	6	1	2	4
sum	0	3	9	10	12	16

 

  위의 arr 배열의 인덱스 i번부터 j번까지의 부분합을 구하고자 한다면, sum[j+1] - sum[i]가 될것입니다.

int sum[6] = {0, 6, 3, 6, 1, 2, 4};

// arr의 누적합 저장
for (int i = 1; i <= 5; i++)
{
	sum[i] = sum[i-1] + sum[i];
}

// arr의 인덱스 2부터 4까지의 합
// sum[j+1] - sum[i]
int p_sum = sum[5] - sum[2];

 

 

 

2.  2차원 배열

---

  2차원 배열도 sum[i][j]에는 arr[0][0] 부터 arr[i-1][j-1]까지의 합을 담아주면 됩니다.

 

// sum 배열 0으로 채우기
int sum[][] = new int[5][5];
for (int i = 0; i < 5; i++)
{
	Arrays.fill(sum[i], 0);
}


// sum 배열 데이터 채우기
for (int i = 1; i <= 4; i++)
{
	for (int j = 1; j <= 4; j++)
    {
    	sum[i][j] = arr[i-1][j-1] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
    }
}

  sum 배열은 위와같은 2중 for문으로 채울 수 있습니다.

 

  arr의 (x1, y1) 부터 (x2, y2) 까지의 합은 아래와 같습니다.

sum[x2+1][y2+1] - sum[x1][y2+1] - sum[x2+1][y1] + sum[x1][y1]

 

 

---

 

이렇게 누적합 알고리즘에 대해서 알아보았습니다.

 

짠!