자바 [Algorithm] 알고리즘 - 구간 합

구간 합 

• 구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.
• 코딩 테스트에서 사용 빈도가 높으니 꼭 알아야 한다.

구간 합의 핵심 이론

• 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다.
• 배열 A가 있을 때 합 배열 S를 구하는 공식
  • S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i] // A[0] 부터 A[i]까지의 합

---

합 배열 S를 만드는 공식

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

---

i에서 j까지 구간 합 구하는 공식

S[j] - S[i-1]

---

A[2] ~ A[5] 구간 합을 합 배열로 구하는 과정

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]

---

문제) 구간 합 구하기

• 난이도 : 실버3
• 백준 온라인 저지 : https://www.acmicpc.net/problem/11659

문제 분석

문제에서 수의 개수와 합을 구하는데 횟수는 최대 100,000이다. 게다가 구간마다 합을 매번 계산하면 0.5초 안에 모든 구간 합 계산을 끝낼 수 없다. 이럴 때 바로 구간 합을 이용해야한다.

코드 구현

package Doit.Chap02.PrefixSum;

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

public class Baek11659 {
    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());

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        long[] D = new long[N+1];

        for(int i=1; i<=N; i++){
            D[i] = D[i-1] + Integer.parseInt(stringTokenizer.nextToken());
            // 입력 수 배열 : 5 4 3 2 1
            // 구간 합 배열 : 5 9 12 14 15
        }

        for(int i=0; i<M; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int a = Integer.parseInt(stringTokenizer.nextToken());
            int b = Integer.parseInt(stringTokenizer.nextToken());
            System.out.println(D[b] - D[a-1]);
        }
    }
}

---

문제) 구간 합 구하기2

• 난이도 : 실버1
• 백준 온라인 저지 : https://www.acmicpc.net/problem/11660

문제 분석

• 2차원 구간 합 배열 D[X][Y] 정의
  • D[X][Y] = 원본 배열의 (0,0)qnxj (X,Y)까지의 사각형 영역 안에 있는 수의 합
• D[i][j]의 값을 채우는 구간 합 공식
  • D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j]

코드 구현

package Doit.Chap02.PrefixSum;

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

public class Baek11660 {
    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());

        int[][] A = new int[N+1][N+1]; // 공식 사용을 위해 배열 1칸 더 크게 설정
        int[][] D = new int[N+1][N+1]; // 공식 사용을 위해 배열 1칸 더 크게 설정

        for(int i=1; i<=N; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for(int j=1; j<=N; j++){
                A[i][j] = Integer.parseInt(stringTokenizer.nextToken());
            }
        }

        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++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int x1 = Integer.parseInt(stringTokenizer.nextToken());
            int y1 = Integer.parseInt(stringTokenizer.nextToken());
            int x2 = Integer.parseInt(stringTokenizer.nextToken());
            int y2 = Integer.parseInt(stringTokenizer.nextToken());

            int result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
            System.out.println(result);
        }
    }
}