백준 알고리즘 11660번

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

import java.io.*;
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 dataN = Integer.parseInt(stringTokenizer.nextToken()); // 배열크기
        int quizN = Integer.parseInt(stringTokenizer.nextToken()); // 질의개수

        long[][] dataArray = new long[dataN + 1][dataN + 1]; // 원본 배열
        long[][] prefixSum = new long[dataN + 1][dataN + 1]; // 구간 합 배열

        for (int i = 1; i < dataArray.length; i++) { // 원본 배열 생성
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            for (int j = 1; j < dataArray[i].length; j++) {
                dataArray[i][j] = Long.parseLong(stringTokenizer.nextToken());
            }
        }

        for (int i = 1; i < prefixSum.length; i++) { // 구간 합 배열 생성
            for (int j = 1; j < prefixSum[i].length; j++) {
                prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]+dataArray[i][j];
            }
        }

        for (long[] temp : dataArray) {
            for (long temp1 : temp)
                System.out.print(temp1 + " ");
            System.out.println();
        }

        for (int i = 0; i < quizN; 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());

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

1. 구간 합 VS 부분 합

- Prefix sum(구간 합) : 구간 합이란 수들의 나열에서 특정 구간의 합을 의미한다. 구간 합 알고리즘은 보통 1차원배열에서 i~k 인덱스 사이의 값들의 합을 구하는데 사용한다.

 

- Partial sum(부분 합) : 부분 합이란 구간 합과 달리 처음부터 특정인덱스까지의 합을 의미한다. 즉 0~k 인덱스 사이의 값들의 합을 의미한다.

 

2. 구간 합 알고리즘

•  반복문을 사용하여 i~k사이의 값을 더하는 알고리즘의 시간복잡도는 O(n)이다.
•  이 같은 알고리즘을 사용할 경우 n의 값이 클 경우 이를 정해진 시간 내에 해결할 수 없다.
•  하지만 구간 합 알고리즘을 사용하여 구간합을 구하는 경우 O(1)의 성능을 갖는다.
•  구간 합 알고리즘은 현재 진행단계까지의 인덱스까지 값의 합을 저장하는 sum[]배열을 사용한다.
•  j번째 바로 앞까지의 총합에 arr[j] 값을 더하면 j번째까지의 총합을 의미하므로 sum[j] = sum[j-1] + arr[j] 로 표현할 수 있다.