구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.
구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다. 배열 A가 있을 때 합 배열 S는 다음과 같이 정의한다.
합 배열 S의 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] // A[0]부터 A[i]까지의 합
합 배열은 기존의 배열을 전처리한 배열로, 이렇게 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다. 합 배열은 다음과 같은 간단한 공식으로 만들 수 있다.
합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]
이렇게 구현된 합 배열을 이용하여 구간 합 역시 쉽게 구할 수 있다. i에서 j까지 구간 합을 구하는 공식은 다음과 같다.
구간 합을 구하는 공식
S[j] - S[i-1]
배열 A[2]부터 A[5]까지의 구간 합을 합 배열을 통해 구하고 싶을 때 A[0] + ... + A[5] 에서 A[0] + A[1] 을 빼면 구간 합 A[2] + ... + A[5] 가 나오므로 S[5]에서 S[1]을 빼면 구간 합을 쉽게 구할 수 있다.합 배열만 미리 구해 두면 구간 합은 한 번의 계산으로 구할 수 있는 것이다. 합 배열과 구간 합 공식을 적재적소에 활용하면 코딩 테스트에서 시간 복잡도를 줄이는 데 많은 도움이 된다.
[백준 11659번] 구간 합 구하기
https://www.acmicpc.net/problem/11659
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int n = Integer.parseInt(stringTokenizer.nextToken());
int m = Integer.parseInt(stringTokenizer.nextToken());
long[] arr = new long[n + 1];
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 1; i <= n; i++) {
arr[i] = arr[i-1] + Integer.parseInt(stringTokenizer.nextToken());
}
for (int k = 0; k < m; k++) {
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int i = Integer.parseInt(stringTokenizer.nextToken());
int j = Integer.parseInt(stringTokenizer.nextToken());
System.out.println(arr[j] - arr[i-1]);
}
}
}
[백준 11660번] 구간 합 구하기 5
https://www.acmicpc.net/problem/11660
구간 합 배열이 1차원에서 2차원으로 확장되었다. 2차원 구간 합 배열은 다음과 같이 정의한다.
2차원 구간 합 배열 D[X][Y] 정의
D[X][Y] = 원본 배열의 (0, 0)부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합
1. 2차원 구간 합 배열의 1행, 1열부터 구한다.
D[i][1] = D[i-1][1] + A[i][1]
D[1][j] = D[1][j-1] + A[1][j]
2. 이를 통해 나머지 2차원 구간 합 배열을 채운다.
D[i][j]의 값을 채우는 구간 합 공식
D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]
3. 질의가 2 2 3 4라면 (3, 4) 구간 합에서 (1, 4) 구간 합, (3, 1) 구간 합을 뺀 다음 중복하여 뺀 (1, 1) 구간 합을 더하면 된다. 공식은 다음과 같다.
질의 X1, Y1, X2, Y2에 대한 답을 구간 합으로 구하는 방법
D[X2][Y2] - D[X1 - 1][Y2] - D[X2][Y1 - 1] + D[X1 - 1][Y1 - 1]
코드로 구현하면 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[][] A = new int[n+1][n+1];
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= n; j++) {
A[i][j] = Integer.parseInt(st.nextToken());
}
}
int[][] D = new int[n+1][n+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// 구간 합 구하기
D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j];
}
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
// 구간 합 배열로 정답 도출
int result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
System.out.println(result);
}
}
}
[백준 10986번] 나머지 합
https://www.acmicpc.net/problem/10986
구간 합 S[j] - S[i-1] 을 M으로 나눈 나머지가 0인 (i, j) 개수를 구하는 문제이다. 식을 정리하면 다음과 같이 나타낼 수 있다.
- (S[j] - S[i-1]) % M = 0
- (S[j] % M) - (S[i-1] % M) = 0
- S[j] % M = S[i-1] % M
즉 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트 후 S[i]와 S[j]가 같은 (i, j) 쌍을 찾으면 된다. 이를 단계적으로 표현하면 다음과 같다.
1. A 배열의 합 배열 S를 생성한다.
배열 A가 1, 2, 3, 1, 2로 되어 있을 때 합 배열 S 1, 3, 6, 7, 9를 생성한다.
2. 합 배열 S의 모든 값을 M으로 나머지 연산을 수행해 값을 업데이트 한다.
합 배열은 %M 연산 후 1, 0, 0, 1, 0 으로 변한다.
3. 우선 변경된 합 배열에서 원소 값이 0인 개수만 세어 정답 변수에 더한다. 이는 즉 원본 배열의 0부터 i까지의 구간 합이 M으로 나누어 떨어진다는 뜻이기 때문이다.
4. 변경된 합 배열에서 원소 값이 같은 인덱스의 개수, 즉 나머지 값이 같은 합 배열의 개수를 센다. 변경된 합 배열에서 원소 값이 같은 2개의 원소를 뽑는 모든 경우의 수를 구하여 정답에 더한다. 위의 예에서는 0이 3개, 1이 2개이므로 3C2, 2C2로 경우의 수를 더하면 된다.
- 나머지 값이 같은 인덱스의 수를 저장하기 위해 배열 C를 생성한다. M으로 나눈 나머지는 0부터 M-1 까지 가능하므로 배열의 크기는 M으로 설정한다.
- 임의의 수 nC2의 수식은 n * (n-1) / 2 가 된다. 그러므로 C[i] * (C[i] - 1) / 2 의 값을 구하면 된다.
이를 코드로 표현하면 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long[] S = new long[n]; // 합 배열
long[] C = new long[m]; // 나머지 값이 같은 인덱스 수 저장
long answer = 0;
// 합 배열 생성
S[0] = sc.nextInt();
for (int i = 1; i < n; i++) {
S[i] = S[i-1] + sc.nextInt();
}
for (int i = 0; i < n; i++) { // 합 배열의 모든 값에 % m 연산 수행
int remainder = (int) (S[i] % m);
// 0 ~ i 까지의 구간 합 자체가 0일 때 정답에 더하기
if(remainder == 0) answer++;
// 나머지가 같은 인덱스의 개수 카운팅하기
C[remainder]++;
// 예를 들어 나머지가 0인 수(C[0])의 개수 추가 (C[0]의 값 + 1)
}
for (int i = 0; i < m; i++) {
// 나머지가 같은 인덱스 중 2개를 뽑는 경우의 수 더하기
if(C[i] > 1)
answer += C[i] * (C[i] - 1) / 2;
}
System.out.println(answer);
}
}
[참고 자료]
Do it! 알고리즘 코딩 테스트 자바 편
https://velog.io/@beheon/%EA%B5%AC%EA%B0%84-%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%982
https://velog.io/@isohyeon/Java-%EB%B0%B1%EC%A4%80-10986-%EB%82%98%EB%A8%B8%EC%A7%80-%ED%95%A9
'알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
| 버블 정렬 (Bubble sort) (0) | 2024.05.15 |
|---|---|
| 스택과 큐 (1) | 2024.05.15 |
| 슬라이딩 윈도우 (0) | 2024.05.11 |
| 투 포인터 (0) | 2024.05.10 |
| 배열과 리스트 (0) | 2024.05.09 |
