[Java]1차원, 2차원 배열의 구간 합 구하기

1. 1차원 배열의 구간 합 구하기

구간 합을 구하기 위해서는 다양한 방법이 있겠지만, 합 배열을 이용하여 구하는 방법이 있다.

int[] numbers = {1,2,3,4,5}; // 정수형 배열 선언
int[] sum = new int[numbers.length]; // numbers 배열의 합 배열 선언

//sum[i] 는 numbers[0] 부터 numbers[i] 까지 모두 더한 값이다.
//예를 들면, sum[3] = numbers[0] + numbers[1] + numbers[2] + numbers[3] 이다.

sum[0] = numbers[0]; // 인덱스 0의 값은 두 배열 모두 동일하다.

// 반복문을 통해 sum 배열을 채워준다.
for (int i = 1; i < sum.length; i++) {
	sum[i] = sum[i - 1] + numbers[i];
}

// 이 과정을 통해 sum = {1,3,6,10,15}; 의 배열을 얻을 수 있다.
/* 어렇게 얻은 sum 배열을 이용해 
 numbers 배열의 index i 에 해당하는 값부터 index j 에 해당하는 값까지 합을 구할 수 있다.
 '구간 합' = sum[j] - sum[i - 1]; 
*/

// index 1 부터 index 3까지 구간 합
sum[3] - sum[1 - 1];

위 방법을 통해 1차원 배열의 구간 합을 구할 수 있다.

2. 2차원 배열의 합 구하기

2차원 배열도 구간 합 공식을 통해 합을 구할 수 있다.

int[][] numbers = {
					{1,2,3,4},
                    {2,3,4,5},
                    {3,4,5,6},
                    {4,5,6,7}
                    			}; // 2차원 배열 선언

int[][] sum = new int[numbers.length][numbers[0].length] // 합배열 선언

/*
	2차원 합배열을 구하기 위해서는 sum[0][i] 와 sum[0][j] 까지를 반복문으로 구하고
    이후에 이를 이용하여 나머지 합 배열을 완성한다.
		*/
    
sum[0][0] = numbers[0][0]; // (0. 0) 인덱스에 해당하는 값은 두 배열 모두 같다.

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

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

for (int i = 1; i < sum.length; i++) {
	for (int j = 1; j < sum[0].length; j++) {
    	sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + numbers[i][j];
    }
}
// 위 반복문을 통해 sum 배열에 값을 넣을 수 있다. 아래와 같이 데이터가 넣어질 것이다.
/*
	sum = {
    		{1,3,6,10},
            {3,8,15,24},
            {6,15,27,42},
            {10,24,42,64}
    						};
		*/
    
/* 위 배열을 통해 구간 합을 구하는 공식은 다음과 같다.
	(a1, a2) 인덱스 값부터 (b1, b2) 인덱스 값까지 합을 구하는 공식
    sum[b1][b2] - sum[a1 - 1][b2] - sum[b1][a2 - 1] + sum[a1 - 1][a2 - 1]
    	*/
        
// 따라서 (1, 1) 인덱스 값부터 (2,3) 인덱스 값까지 구하는 방식은 아래와 같다.

int answer = sum[2][3] - sum[1 - 1][3] - sum[2][1 - 1] + sum[1 - 1][1 - 1];

return answer; // 27

위 방식을 통해 2차원 배열의 구간 합을 구할 수 있다.

(참고 : 알고리즘 코딩테스트 자바 편(이지스 퍼블리싱) / 김종관 저)