1. 누적 합은 언제 쓰는가? |
A[i] + A[i+1] + A[i+2] + A[i+3] + A[i+4] + A[i+5] 처럼 배열 중 일부분의 구간의 sum을 구하는 일을 여러번 하는 경우
예를들어 인덱스 0~5의 합, 인덱스 1~6의 합, 인덱스 2~7의 합, 인덱스 3~8의 합... 중 가장 큰 값을 묻는 경우
2. 누적합 알고리즘을 안쓴다면? |
for문을 이용해 인덱스 0부터 5까지 5번 반복해서 더한 후 값을 저장하고, 또 1부터 6까지 5번 반복해서 더한 후 값을 저장하고... 반복
이렇게 하면 한번의 for문은 O(n)이지만 이걸 자주 반복하는 경우 m회 반복한다면 O(nm)이 되므로 효율적이지 못함
3. 누적합 알고리즘을 쓴다면? |
1) 1차원 배열
A배열이 아닌 S배열을 새로 만든 후 값을 입력받을때마다 S배열에는 A배열의 누적합을 저장함
S[0]에는 A[0]의 값을
S[1]에는 A[0] + A[1]의 값을 // S[0] + A[1]과 같으므로 S[i-1] + A[i]
S[2]에는 A[0] + A[1] + A[2]의 값을 // S[1] + A[2]과 같으므로 S[i-1] + A[i]
S[3]에는 A[0] + A[1] + A[2] + A[3]의 값을 저장하는 것
그리고 만약 A[2] ~ A[6]의 누적합을 알고싶다면 for문으로 5회 반복하는 것이 아닌
S[6] - S[1]을 해줘서 O(1)로 바로 해결 가능
코드로 구현한다면
// 0은 비워두고 1부터 사용해야 index-1 코드 작성할때 코드가 짧고 단순해짐
// 그러므로 N+1칸의 공간이 필요
vector<int> a(n + 1, 0);
vector<int> s(n + 1, 0);
// 누적합 배열 만들기
for (int i = 1; i < n + 1; i++) {
cin >> a[i]; // arr을 입력받으면서
s[i] = s[i - 1] + a[i]; // 동시에 누적합도 연산함
/* 혹은 a벡터 없이 ps벡터만으로 쓰려면
std::cin >> ps[i];
ps[i] += ps[i-1];
처럼 간결하게 쓸 수도 있음
*/
}
// x~y의 누적합 출력하기
int x, y;
cin >> x >> y;
if (x <= 0) cout << s[y]; // 그냥 예외처리
else cout << s[y] - s[x - 1]; // 여기가 핵심
2) 2차원 배열
2차원 arr배열의 누적 합 배열인 sum의 배열은 sum[i][j]에 arr[0][0] ~ arr[i][j]의 합이 들어감
예를들어 sum[1][1]에는 arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1]이 들어감
그리고 만약 위 빨간 네모구간인 arr[1][2] ~ arr[4][4]구간의 값들의 합을 구하고 싶다면
sum[4][4] - sum[4][1] - sum[0][4] + sum[0][1] 을 해주면 해결 가능
코드로 구현한다면
// 마찬가지로 0은 비워두고 1부터 사용해야 코드가 짧아짐
// 즉 row + 1칸의 공간, col + 1칸의 공간이 필요
vector<vector<int>> a(row + 1, vector<int>(col + 1, 0));
vector<vector<int>> s(row + 1, vector<int>(col + 1, 0));
// 2차원 누적합 배열 만들기
for (int i = 1; i < row + 1; i++) {
for (int j = 1; j < col + 1; j++) {
cin >> a[i][j];
s[i][j] = s[i - 1][j] + s[i][j - 1] + a[i][j] - s[i - 1][j - 1];
}
}
// [x1][y1] ~ [x2][y2]의 누적합 출력하기
int x1, y1;
int x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
// 예외처리 구간
if (x1 <= 0 && y1 <= 0) cout << s[x2][y2];
else if (x1 <= 0) cout << s[x2][y2] - s[x2][y1 - 1];
else if (y1 <= 0) cout << s[x2][y2] - s[x1 - 1][y2];
// 여기가 핵심
else cout << s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];