java/ 기존 배열의 합 배열을 만들어 구간 합 구하기

 

 

원본 배열에 대한 합 배열을 미리 생성해 가져다 쓰는 기법으로 입력 값의 범위가 넓을 때 시간 복잡도를 줄이기 위해 사용한다.

 

 

일차원 배열

 

원본 배열 int[] arr 생성

 

int[] arr = new int[] {1, 3, 5, 7, 9, 11};

 

생성 결과

 

1

3

5

7

9

11

 

 

---

 

합 배열 int[] sum 생성

 

위와 같이 존재하는 원본 배열 arr에 대해 합 배열 int[] sum을 생성한다.

 

int[] sum = new int[arr.length];
sum[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
    sum[i] = sum[i - 1] + arr[i];
}

 

생성 결과

 

1

4

9

16

25

36

 

---

 

합 배열을 이용해 배열의 구간 합 구하기

 

1

3

5

7

9

11

 

원본 배열에서 위와 같은 구간의 합(7 + 9 + 11)을 구하는 경우를 알아본다.

 

주어진 원본 배열에서 합 배열을 구하는 과정을 풀어쓰면 다음과 같다.

 

sum[0] = arr[0]
sum[1] = arr[0] + arr[1]
sum[2] = arr[0] + arr[1] + arr[2]
sum[3] = arr[0] + arr[1] + arr[2] + arr[3]
sum[4] = arr[0] + arr[1] + arr[2] + arr[3] + arr[4] 
sum[5] = arr[0] + arr[1] + arr[2] + arr[3] + arr[4] + arr[5]

 

따라서 arr[3]부터 arr[5]까지의 구간 합을 구할 경우 배열의 요소에 arr[3]이 포함되지 않은 sum[2]를 sum[5]에서 빼주어 arr[3] + arr[4] + arr[5] 까지의 합을 얻을 수 있게 된다.

 

1

4

9

16

25

36

sum[5] - sum[2] = 36 - 9 = 27

 

 

원본 배열의 인덱스 from 부터 인덱스 to 까지의 합을 구하는 식

sum[to] - sum[from-1]

 

---

 

e.g. 원본 배열 arr의 인덱스 3부터 인덱스 5까지의 구간 합 구하기

//arr[3] ~ arr[5]까지의 구간 합
int partSum = sum[5] - sum[2];

 

실행 결과

 

27

 

---

 

2차원 배열

 

일차원 배열과 같은 방식으로 2차원 배열의 구간 합 역시 구할 수 있다.

 

 

원본 배열 int[][] arr 생성

 

int[][] arr = new int[4][4];
for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 4; j++) {
        arr[i][j] = (i+j+1);
    }
}

 

생성 결과

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

 

---

 

구간 합 배열 int[][] sum 생성

 

위와 같이 존재하는 원본 배열 arr에 대해 구간 합 배열 int[][] sum을 생성한다.

 

int[][] sum = new int[4][4];

 

 

생성된 sum 배열의 각 요소는 다음과 같은 형식으로 값이 들어가야 한다.

 

sum[1][1] = arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1]

 

arr[0][0]	arr[0][1]
arr[1][0]	arr[1][1] sum[1][1]

 

sum[2][1] = arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1] + arr[2][0] + arr[2][1]

arr[0][0]	arr[0][1]
arr[1][0]	arr[1][1]
arr[2][0]	arr[2][1] sum[2][1]

 

 

따라서 먼저 sum[0][0] = arr[0][0]의 값을 할당해주고,

sum[0][j] 라인과 sum[i][0] 라인에 일차원 배열에서 합 배열을 구했던 것과 같은 방식으로 값을 할당한다.

 

//초기값 할당
sum[0][0] = arr[0][0];

for (int j =1; j < 4; j++) {
    sum[0][j] = sum[0][j-1] + arr[0][j];
}
for (int i = 1; i < 4; i++) {
    sum[i][0] = sum[i - 1][0] + arr[i][0];
}

 

할당 결과

1	3	6	10
3
6
10

 

이제 주어진 초기값에 따라 루프를 돌면서 sum 배열의 모든 요소에 값을 할당해야 한다.

 

---

 

sum[1][1] 구해보기

 

 

sum[0][0] = 1	sum[0][1] = 3	sum[0][2] = 6	sum[0][3] = 10
sum[1][0] = 3	sum[1][1]
sum[2][0] = 6
sum[3][0] = 10

 

 

sum[0][0] = arr[0][0]

sum[0][1] = arr[0][0] + arr[0][1]

sum[1][0] = arr[0][0] + arr[1][0]

 

sum 배열에서 할당된 값은 위와 같이 구해진 것이고, sum[1][1]의 값을 구하기 위해서는 다음과 같은 식이 완성되어야 한다.

 

sum[1][1] = arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1]

 

그리고 위의 식은 다음과 같이 나타낼 수 있다.

 

sum[1][1]

= sum[0][1] + sum[1][0] + arr[1][1] - sum[0][0]
= (arr[0][0] + arr[0][1]) + (arr[0][0] + arr[1][0]) + arr[1][1] - (arr[0][0])
= arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1]

 

---

 

sum[2][1] 구해보기

 

sum[0][0] = 1	sum[0][1] = 3	sum[0][2] = 6	sum[0][3] = 10
sum[1][0] = 3	sum[1][1] = 8
sum[2][0] = 6	sum[2][1]
sum[3][0] = 10

 

sum[2][1]의 값 역시 위와 같은 식으로 구하게 되면,

 

sum[2][1]

= sum[1][1] + sum[2][0] + arr[2][1] - sum[1][0]
= (arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1]) + (arr[0][0] + arr[1][0] + arr[2][0]) + arr[2][1] - (arr[0][0] + arr[1][0])
 = arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1] + arr[2][0] + arr[2][1]

 

arr[0][0] = 1	arr[0][1] = 2
arr[1][0] = 2	arr[1][1] = 3
arr[2][0] = 3	arr[2][1] = 4

 

위의 요소의 합이 sum[2][1]에 할당된다.

 

---

 

sum[i][j] 구하기

 

sum[i][j] = sum[i-1][j] + sum[i][j-1] + arr[i][j] - sum[i-1][j-1]

 

for (int i = 1; i < 4; i++) {
    for (int j = 1; j < 4; j++) {
        sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + arr[i][j] - sum[i - 1][j - 1];
    }
}

 

할당 결과

 

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64