[알고리즘/Java] 구간 합(Prefix Sum)과 관련 예제(BOJ-11659)

[ 1 ] 정수 배열 A에서 특정 구간(i ~ j) 내 모든 원소의 합을 구하라

특정 배열이 주어지고 위와 같은 질문을 받는다면, 우리는 어떻게 특정 구간 내 모든 원소의 합을 구할 수 있을까?

시간 제한이 없고 배열 원소의 수가 적다면 단순히 선형 탐색으로 i ~ j 까지의 특정 구간 내 원소의 합을 구할 수 있을 것이다.

하지만, 배열 내 원소의 수가 매우 많고, 계산해야 할 특정 구간도 많이 주어진다면 위와 같은 선형 탐색은 오랜 시간이 소요될 것이다.

 

[ 2 ] 구간 합(Prefix Sum)

[2 - 1] 정의

구간 합 알고리즘을 활용하면 선형 탐색으로 O(n)이 소요되던 시간 복잡도를 O(1)으로 줄일 수 있다. 어떻게 이것이 가능한가?

 

우선 A라는 정수 배열이 있을 때 S라는 '합 배열'을 정의해야 한다.

- S[i] = A[0] + A[1] + A[2] + A[3] + A[4] + ... + A[i-1] + A[i]

 

합 배열 S

 

합 배열 S[i]에는 배열 A의 0번째 인덱스 원소부터 i번째 인덱스 원소까지의 합에 대한 정보가 담겨있다. 즉, 합 배열을 미리 구해 놓음으로써 더 이상 선형 탐색을 할 필요가 없어지고 시간 복잡도가 O(1)으로 줄어드는 것이다.

 

 

[2- 2] 합 배열 S 만들기

합 배열 S는 다음과 같은 공식으로 만들 수 있다. 합을 저장하는 기본 정수 배열의 이름은 A라고 가정한다.

 

- S[i] = S[i-1] + A[i]

 

※ 매우 간단한 공식이지만, S[i-1]에 접근하므로 소스 코드로 구현할 때 반복문의 범위에 주의해야 한다.

 

 

[2 - 3] 특정 구간(i~j)의 구간 합을 구하기

배열 A의 i ~ j까지의 구간 내 원소의 합을 구하기 위해서는 다음과 같은 공식을 활용한다.

 

 S[ j ] - S[ i-1 ]

 

예시는 다음과 같다.

만약 위 그림에서 A[2] ~ A[4]까지의 합을 구한다고 가정하자.

S[4] = A[0] + A[1] + A[2] + A[3] + A[4] 이므로 S[4]에서 A[0] + A[1]을 빼면 A[2] ~ A[4]까지의 합이 나온다.

A[0] + A[1] = S[1] 이므로 결국 A[2] ~ A[4]까지의 합은 S[4] - S[1]이고,  S[ j ] - S[ i-1 ] 공식에 부합한다.

 

 

[ 3 ]  예제 - 백준 11659 Java 풀이

문제 출처: https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

[문제]

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

[입력]

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

[출력]

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

[풀이]

합 배열 S 만들기: S[i] = S[i-1] + A[i]

구간 합 구하기:  S[ j ] - S[ i-1 ]

 

위 공식을 활용하여 문제를 해결한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
		
		long[] S = new long[N+1];
		
		st = new StringTokenizer(br.readLine());
		
		for(int i = 1; i <= N; i++)
		{
			S[i] = S[i-1] + Integer.parseInt(st.nextToken());
		}
		
		for(int j = 0; j < M; j++)
		{
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			System.out.println(S[y] - S[x-1]);
		}

	}

}