[알고리즘] 39. 구간합 문제
지난 글에서는 누적합(Prefix Sum)의 기본 개념을 정리했습니다. 이번 글에서는 누적합을 실제 문제에 적용하는 구간합 문제를 정리해보겠습니다.
구간합 문제는 배열에서 특정 구간의 합을 구하는 문제입니다. 처음에는 단순히 반복문으로 더하면 될 것 같지만, 구간 합을 여러 번 구해야 한다면 누적합을 사용해야 훨씬 효율적으로 해결할 수 있습니다.
구간합 문제의 핵심은 누적합을 미리 만들어두고, 원하는 구간의 합을 O(1)에 구하는 것입니다.
1. 구간합이란?
구간합은 배열의 특정 구간에 있는 값들을 모두 더한 결과입니다. 예를 들어 아래 배열이 있다고 하겠습니다.
배열: [1, 2, 3, 4, 5]2번째 값부터 4번째 값까지의 합을 구하면 다음과 같습니다.
2 + 3 + 4 = 9이처럼 특정 시작 위치부터 끝 위치까지의 합을 구하는 문제가 구간합 문제입니다.
구간합은 배열에서 연속된 일부 구간의 합을 의미합니다.
2. 반복문으로 구간합 구하기
가장 단순한 방법은 구간의 시작부터 끝까지 반복문으로 더하는 것입니다.
int[] arr = {1, 2, 3, 4, 5};
int left = 1;
int right = 3;
int sum = 0;
for (int i = left; i <= right; i++) {
sum += arr[i];
}
System.out.println(sum);출력 결과는 다음과 같습니다.
90번 인덱스 기준으로 left = 1, right = 3이면 arr[1], arr[2], arr[3]을 더합니다. 즉 2 + 3 + 4 = 9입니다.
구간합을 한 번만 구한다면 이 방법도 괜찮습니다. 하지만 구간합을 여러 번 구해야 한다면 매번 반복문을 돌기 때문에 느려질 수 있습니다.
3. 구간합 질문이 여러 개라면?
문제에서 구간합을 여러 번 물어보는 경우가 많습니다. 예를 들어 다음과 같은 질문이 있다고 하겠습니다.
배열: [1, 2, 3, 4, 5]
질문 1: 1번부터 3번까지의 합
질문 2: 2번부터 5번까지의 합
질문 3: 3번부터 4번까지의 합각 질문마다 반복문으로 구간을 다시 더하면 비효율적입니다. 배열 길이가 크고 질문 개수가 많다면 시간 초과가 발생할 수 있습니다.
| 방식 | 구간합 1번 | 구간합 M번 |
|---|---|---|
| 반복문 직접 계산 | O(N) | O(N × M) |
| 누적합 사용 | O(1) | O(M) |
이럴 때 누적합을 사용하면 구간합을 빠르게 구할 수 있습니다.
4. 누적합으로 구간합 구하기
누적합 배열을 만들어두면 구간합을 빠르게 계산할 수 있습니다. 입문 단계에서는 1번 인덱스 기준으로 누적합 배열을 만드는 방식이 가장 깔끔합니다.
배열: 1 2 3 4 5
인덱스: 1 2 3 4 5
prefix: 0 1 3 6 10 15prefix[i]는 1번부터 i번까지의 합입니다. prefix[0]은 아무것도 더하지 않은 상태이므로 0입니다.
left부터 right까지의 합은 다음 공식으로 구합니다.
구간합 = prefix[right] - prefix[left - 1]구간합 공식은 prefix[right] - prefix[left - 1]입니다.
5. 1차원 구간합 Java 코드
배열의 구간합을 누적합으로 구하는 기본 코드는 다음과 같습니다.
int[] arr = {1, 2, 3, 4, 5};
int n = arr.length;
int[] prefix = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + arr[i - 1];
}
int left = 2;
int right = 4;
int sum = prefix[right] - prefix[left - 1];
System.out.println(sum);출력 결과는 다음과 같습니다.
92번부터 4번까지의 값은 2, 3, 4입니다. 따라서 구간합은 9입니다.
6. 여러 구간합 질의 처리하기
구간합 질문이 여러 개라면 누적합 배열을 한 번 만든 뒤, 각 질문마다 공식을 적용하면 됩니다.
int[] arr = {1, 2, 3, 4, 5};
int n = arr.length;
int[] prefix = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + arr[i - 1];
}
int[][] queries = {
{1, 3},
{2, 5},
{3, 4}
};
for (int[] query : queries) {
int left = query[0];
int right = query[1];
int sum = prefix[right] - prefix[left - 1];
System.out.println(sum);
}출력 결과는 다음과 같습니다.
6
14
7각 구간의 합은 다음과 같습니다.
- 1번부터 3번까지: 1 + 2 + 3 = 6
- 2번부터 5번까지: 2 + 3 + 4 + 5 = 14
- 3번부터 4번까지: 3 + 4 = 7
7. 구간합 문제의 시간복잡도
누적합을 사용한 구간합 문제는 전처리와 질의 처리로 나누어 생각합니다.
| 작업 | 시간복잡도 |
|---|---|
| 누적합 배열 만들기 | O(N) |
| 구간합 하나 구하기 | O(1) |
| M개의 질의 처리 | O(M) |
| 전체 | O(N + M) |
반복문으로 매번 구간을 직접 더하면 최악의 경우 O(N × M)이 될 수 있습니다. 하지만 누적합을 사용하면 전체를 O(N + M)에 처리할 수 있습니다.
구간합 질의가 많을수록 누적합의 효과가 커집니다.
8. long을 사용해야 하는 경우
구간합 문제에서는 합이 매우 커질 수 있습니다. 배열의 값이 크거나 원소 개수가 많다면 int 범위를 넘을 수 있습니다.
원소 하나의 값: 1,000,000
원소 개수: 100,000
전체 합: 100,000,000,000이 값은 int 범위를 넘습니다. 따라서 이런 경우에는 int[]가 아니라 long[]을 사용해야 합니다.
long[] prefix = new long[n + 1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + arr[i - 1];
}문제에서 입력 값의 범위를 확인하고 합이 커질 수 있다면 long을 사용하는 것이 안전합니다.
구간합은 값이 계속 더해지므로 long 사용 여부를 꼭 확인해야 합니다.
9. 2차원 구간합이란?
구간합은 1차원 배열뿐 아니라 2차원 배열에서도 사용할 수 있습니다. 2차원 구간합은 표나 지도에서 특정 직사각형 영역의 합을 구하는 문제입니다.
1 2 3
4 5 6
7 8 9예를 들어 위 표에서 왼쪽 위 2 × 2 영역의 합은 다음과 같습니다.
1 + 2 + 4 + 5 = 122차원 구간합도 매번 직접 더하면 오래 걸립니다. 그래서 2차원 누적합 배열을 만들어두고 직사각형 영역의 합을 빠르게 구합니다.
10. 2차원 누적합 배열 만들기
2차원 누적합은 현재 위치까지의 직사각형 합을 저장합니다. 1번 인덱스 기준으로 prefix 배열을 만들면 공식이 깔끔해집니다.
prefix[i][j] = (1,1)부터 (i,j)까지의 합2차원 누적합을 만드는 공식은 다음과 같습니다.
prefix[i][j]
= map[i][j]
+ prefix[i - 1][j]
+ prefix[i][j - 1]
- prefix[i - 1][j - 1]위쪽 누적합과 왼쪽 누적합을 더하면 왼쪽 위 영역이 한 번 중복됩니다. 그래서 prefix[i - 1][j - 1]을 한 번 빼줍니다.
2차원 누적합은 위쪽 합과 왼쪽 합을 더하고, 중복된 왼쪽 위 영역을 빼는 방식입니다.
11. 2차원 누적합 Java 코드
2차원 누적합 배열을 만드는 코드는 다음과 같습니다.
int[][] map = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int n = 3;
int m = 3;
int[][] prefix = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
prefix[i][j] = map[i - 1][j - 1]
+ prefix[i - 1][j]
+ prefix[i][j - 1]
- prefix[i - 1][j - 1];
}
}map은 0번 인덱스 기준이고, prefix는 1번 인덱스 기준입니다. 그래서 map[i - 1][j - 1]을 사용합니다.
12. 2차원 구간합 공식
2차원 구간합은 왼쪽 위 좌표와 오른쪽 아래 좌표가 주어졌을 때 직사각형 영역의 합을 구합니다.
왼쪽 위: (x1, y1)
오른쪽 아래: (x2, y2)1번 인덱스 기준에서 2차원 구간합 공식은 다음과 같습니다.
영역 합 =
prefix[x2][y2]
- prefix[x1 - 1][y2]
- prefix[x2][y1 - 1]
+ prefix[x1 - 1][y1 - 1]전체 누적합에서 위쪽 영역과 왼쪽 영역을 빼고, 두 번 빠진 왼쪽 위 영역을 다시 더하는 방식입니다.
2차원 구간합은 빼고 빼고 다시 더하는 구조입니다.
13. 2차원 구간합 Java 코드
2차원 배열에서 특정 직사각형 영역의 합을 구하는 코드는 다음과 같습니다.
int x1 = 1;
int y1 = 1;
int x2 = 2;
int y2 = 2;
int sum = prefix[x2][y2]
- prefix[x1 - 1][y2]
- prefix[x2][y1 - 1]
+ prefix[x1 - 1][y1 - 1];
System.out.println(sum);위 코드는 1행 1열부터 2행 2열까지의 합을 구합니다.
1 2
4 5
합 = 12출력 결과는 다음과 같습니다.
1214. 1차원 구간합과 2차원 구간합 비교
1차원 구간합과 2차원 구간합은 원리는 비슷합니다. 차이는 구간이 선인지, 직사각형 영역인지입니다.
| 구분 | 대상 | 공식 |
|---|---|---|
| 1차원 구간합 | 배열의 left ~ right | prefix[right] - prefix[left - 1] |
| 2차원 구간합 | 직사각형 영역 | 전체 - 위 - 왼쪽 + 중복 |
1차원은 왼쪽 구간만 빼면 됩니다. 2차원은 위쪽 영역과 왼쪽 영역을 빼고, 중복해서 빠진 영역을 다시 더해야 합니다.
15. 구간합 문제에서 자주 하는 실수
구간합 문제를 풀 때는 아래 실수를 조심해야 합니다.
- prefix 배열 크기를 n + 1로 만들지 않는 경우
- 0번 인덱스 기준과 1번 인덱스 기준을 섞는 경우
- prefix[right] - prefix[left - 1] 공식을 잘못 쓰는 경우
- left가 1일 때 prefix[0]을 사용해야 한다는 점을 놓치는 경우
- map[i][j]와 prefix[i][j]의 인덱스 차이를 헷갈리는 경우
- 2차원 구간합에서 마지막 중복 영역을 다시 더하지 않는 경우
- 합이 int 범위를 넘을 수 있는데 int 배열을 사용하는 경우
특히 2차원 구간합에서는 아래 구조를 꼭 기억해야 합니다.
영역 합 = 전체 - 위쪽 - 왼쪽 + 중복 영역구간합 문제의 실수는 대부분 인덱스 기준과 공식에서 발생합니다.
16. 정리
이번 글에서는 구간합 문제를 정리했습니다.
- 구간합은 배열이나 표에서 특정 구간의 합을 구하는 문제이다.
- 구간합 질문이 많다면 누적합을 사용해야 효율적이다.
- 1차원 누적합은 prefix[right] - prefix[left - 1] 공식으로 구간합을 구한다.
- 누적합 배열은 보통 n + 1 크기로 만들고 prefix[0]을 0으로 둔다.
- 누적합 전처리는 O(N), 구간합 질의는 O(1)에 처리할 수 있다.
- 2차원 구간합은 직사각형 영역의 합을 빠르게 구할 때 사용한다.
- 2차원 구간합은 전체에서 위쪽과 왼쪽을 빼고, 중복 영역을 다시 더한다.
- 합이 커질 수 있다면 long을 사용해야 한다.
구간합 문제는 누적합을 제대로 이해했는지 확인하는 대표 유형입니다. 1차원에서는 인덱스 기준을 명확히 잡고, 2차원에서는 영역을 빼고 더하는 구조를 그림처럼 이해하는 것이 중요합니다.
구간합 문제의 핵심은 합을 미리 저장해두고, 구간 질의를 빠르게 처리하는 것입니다.
다음 글 예고
다음 글에서는 차분 배열에 대해 알아보겠습니다.
여러 구간에 같은 값을 더하는 문제를 효율적으로 처리하는 방법, difference 배열과 누적합 복원 과정을 예제로 정리해보겠습니다.
'Problem Solving > Algorithm' 카테고리의 다른 글
| [알고리즘] 40. 차분 배열(Difference Array) (1) | 2026.07.23 |
|---|---|
| [알고리즘] 38. 누적합(Prefix Sum) (0) | 2026.07.21 |
| [알고리즘] 37. 슬라이딩 윈도우 (0) | 2026.07.20 |
| [알고리즘] 36. 투 포인터 (0) | 2026.07.19 |
| [알고리즘] 35. Comparator 완전 정복 (0) | 2026.07.18 |