구간 합: 합 배열을 이용해 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘입니다.
1. 합 배열 S 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[1]
합 배열은 기존 배열을 전처리한 배열입니다.
이렇게 합 배열을 구해놓으면 기존 배열의 일정 범위 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소합니다.
예를들어
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 |
| 배열 A | 15 | 13 | 10 | 7 | 3 | 12 |
| 합 배열 S | 15 | 28 | 38 | 45 | 48 | 60 |
A[i]부터 A[j]까지의 배열을 합 배열 없이 구하는 경우, 최악의 경우는 i가 0이고 j가 N인 경우로 시간 복잡도는 O(N)입니다.
이런 경우 앞에서 알아본 합 배열을 사용하면 O(1)안에 답을 구할 수 있습니다.
이는 아래와같은 공식으로 만들 수 있습니다.
S[i] = S[i-1] + A[i]
아래 표에서 A[2]부터 A[5]까지의 구간 합을 합 배열을 통해 구하는 과정을 봅니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 |
| 배열 A | 15 | 13 | 10 | 7 | 3 | 12 |
| S[5] | ← | → | ||||
| S[1] | ← | → | ← | → |
S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]
S[1] = A[0] + A[1]
S[5] - S[1] = A[2] + A[3] + A[4] + A[5]
S[5] 합 배열 값에서 S[1] 값을 빼면 A[2]부터 A[5]까지의 구간 합을 구할 수 있습니다.
2, 구간 합 구하기 (백준 11659번)
문제: 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
입력: 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.
출력: 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.
예제 입력:
5 3
5 4 3 2 1
1 3
2 4
5 5
예제 출력:
12
9
1
N과 M의 최대가 10만이므로 시간제한 1초 내에 연산을 끝내기위해 합 배열을 사용합니다.
package algorithms.boj.array;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Q11659 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
// 배열길이와 몇개의 구간합을 구할지 입력받는다
int arrayLength = Integer.parseInt(st.nextToken());
int count = Integer.parseInt(st.nextToken());
// 입력받은 배열길이 + 1의 길이의 합배열을 만든다.
long[] S = new long[arrayLength + 1];
st = new StringTokenizer(br.readLine());
// 배열을 입력받으면 바로 합배열로 만들어 저장한다.
for(int i=1; i<S.length; i++){
S[i] = S[i-1] + Integer.parseInt(st.nextToken());
}
// 구간합을 구해야 하는 길이를 입력받고, 합배열 공식을 이용해 해당 구간합을 구한다.
for(int i=0; i<count; i++){
st = new StringTokenizer(br.readLine());
int j = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
System.out.println(S[k] - S[j-1]);
}
}
}
'Algorithm' 카테고리의 다른 글
| 백준 10448번: 유레카 이론 (0) | 2025.04.29 |
|---|---|
| 백준 10158번: 개미 (0) | 2025.03.04 |
