누적합 (BOJ11659, BOJ2167) (java)
1차원 누적합
알고리즘 문제에서 배열의 부분합을 빠르게 구해야 하는 경우에 누적합을 이용하면 연속된 누적합을 O(N)만에 구할 수 있다.
1. S(n) = 배열 a의 1번째 요소 부터 n번째 요소까지의 누적합
2. S(1) = a(1)
**3. S(n) = S(n-1) + a(n) //n이전까지의 부분합 + n번째 숫자**
4. a(start) + a(start+1) + ... + a(end-1) + a(end) = **S(end) - S(start-1**) //S(n-1)을 왼쪽으로 넘겨준 식
누적합 1차원 예제
https://www.acmicpc.net/problem/11659
- arr사이즈 +1만큼 sum배열 선언
- S(n) = S(n-1) + a(n)성질 이용해서 arr 배열 만들때 sum배열도 만들어주기
- S(end) = S(start-1)성질 이용해서 구간합 구하면 끝 !
- 입력받은 배열 arr
- 누적합 sum
예를 들어, arr[2]~[4] 사이의 누적합을 구하고 싶다면(4+3+2) , sum[4]-sum[1]을 해주면 된다. (arr에서는 인덱스 1부터 세어주고, sum에서는 0부터 센다.)
BOJ11659 풀이
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class boj11659 {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken()); // n개의 정수
int m = Integer.parseInt(st.nextToken()); // m개의 구간합
int[] arr = new int[n];
int[] sum = new int[n+1];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < arr.length; i++) { //arr에 n개의 숫자 초기화
arr[i] = stoi(st);
sum[i+1] = sum[i]+arr[i];//sum[1] = sum[0]+arr[1]
}
// //구간합 배열 구하기
// for (int i = 1; i <arr.length+1; i++) { //sum은 idx 1부터 arr의 length만큼 반복
// for(int j=0;j<=i-1;j++) {//j는 0, 01, 012, 이렇게 더해나가야함, i가 1부터 시작하니까 -1 해줘야함
// sum[i] += arr[j];
// }
// }
while(m-->0) {
st = new StringTokenizer(br.readLine(), " ");
int start = stoi(st);
int end = stoi(st);
bw.write(sum[end]-sum[start-1]+"\\n"); //arr[start]~arr[end]의 구간합 = sum[end]-sum[start-1]
}
bw.flush();
br.close();
bw.close();
}
static int stoi(StringTokenizer st) {
return Integer.parseInt(st.nextToken());
}
}
2차원 누적합
2차원의 누적합을 구하는건 1차원이랑 조금 다르다. 초록색 범위인 (2,2) ~ (3,3)의 누적합을 구하고 싶다면, 가로 누적합과 세로 누적합을 다 더한S에서, S(3,3) - 초록색 범위왼쪽 열 - 초록색 범위 위의 행 + 행과 열에서 총 2번빠졌기 때문에 마지막으로 행과 열이 만나는 지점을 한번 더해준다.
S(i,j)는 i,j까지의 누적합이기 때문에 결과적으로는 S(3,3) - S(3,1) -S(1,3) + S(1,1)을 해주면 된다.
sum(x1, y1, x2, y2) = S(x2, y2) - S(x1 - 1, y2) - S(x2, y1 - 1) + S(x1 -1, y1 -1)
2차원 누적합 예제
https://www.acmicpc.net/problem/2167
- S(n) = S(n-1) + a(n)성질 이용해서 가로로 누적합들을 구해준다. (이때, 1차원 처럼 앞의 인덱스 0번째자리에 0을 다 넣어줘야 하기 때문에 arr[n][m+1]이 된다.)
- 아까 구한 가로 누적합들을 바탕으로, 세로 누적합을 또 구해준다 (여기도 0번째자리에 0넣어줘야 하기때문에 last[n+1][m+1]이 된다.)
- 구한 누적합들을 바탕으로 S(x2, y2) - S(x1 - 1, y2) - S(x2, y1 - 1) + S(x1 -1, y1 -1)성질을 이용해서 구간합을 구한다.
- 입력받은 배열
- 가로 누적합
- 세로 누적합
예를들어, (1,1)과 (2,3)사이의 누적합은 S[2][3] - S[0][3] - S[2][0] + S[0][0] 으로 구할 수 있고
(1,3)과 (2,3)사이의 누적합은 S[2][3] - S[0][3] - S[2][2] + S[0][2] 로 구할 수 있다.
앞의 입력받은 배열에서 (x1-1, y1-1) (x2-1, y2-1)의 누적합을 보면 일치하는 것을 알 수 있다.
BOJ2167 예제
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class BOJ2167 {
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = stoi(st.nextToken()); // n개의 정수
int m = stoi(st.nextToken()); // m개의 구간합
int[][] arr = new int[n][m];
int[][] sum = new int[n][m+1];
int[][] last = new int[n+1][m+1];
for(int i=0;i<n;i++) { //가로 누적합
st = new StringTokenizer(br.readLine(), " ");
for (int j = 0; j < m; j++) {
arr[i][j] = stoi(st.nextToken());
sum[i][j+1] = sum[i][j] + arr[i][j];
}
}
for(int j=0;j<m;j++) { //가로 누적합에서 세로 누적합
for (int i = 0; i < n; i++) {
last[i+1][j+1] = last[i][j+1] + sum[i][j+1];
}
}
int k = Integer.parseInt(br.readLine());
while(k-->0) { // 번 (x1,y1)와 (x2,y2)사이의 누적합을 구한다.
st = new StringTokenizer(br.readLine(), " ");
int x1 = stoi(st.nextToken());
int y1 = stoi(st.nextToken());
int x2 = stoi(st.nextToken());
int y2 = stoi(st.nextToken());
bw.write(last[x2][y2]-last[x1-1][y2]-last[x2][y1-1]+last[x1-1][y1-1] + "\\n");
}
bw.flush();
br.close();
bw.close();
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
Comments