[알고리즘 이론] 1. 누적합

알고리즘 이론들을 모아서 쉬운 것 부터 순서대로 작성하면서 공부하겠습니다.

저는 자바로 코딩테스트를 응시하기 때문에 자바 코드만 작성하고, 파이썬에 대해서 알고 싶으시면 참고 자료의 링크로 이동하시면 자세하게 설명되어 있습니다.

또한, 자바로 백준 문제를 풀기 위한 정보는 아래 게시글을 통해 꼭 한 번 보면 좋습니다.

https://nahwasa.com/entry/%EC%9E%90%EB%B0%94%EB%A1%9C-%EB%B0%B1%EC%A4%80-%ED%92%80-%EB%95%8C%EC%9D%98-%ED%8C%81-%EB%B0%8F-%EC%A3%BC%EC%9D%98%EC%A0%90-boj-java

알고리즘 문제 기초부터 훈련까지 문제 추천
https://covenant.tistory.com/224

문제의 난이도는 브론즈 < 실버 < 골드 < 플래티넘 순이며, 숫자가 낮을수록 같은 계급에선 어려운 문제입니다.

1차원 배열

누적합

• 0번째 인덱스부터 N번째 인덱스까지 탐색하면서 인덱스 가 i일 때 0번째 인덱스 값부터 i번째 인덱스 값을 합친것을 말한다.

코드

public class Main {

    public static void main(String[] args){
        int[] array = {1, 8, 7, 4, 3, 5, 6};
        int n = array.length;
        int[] prefix_sum = new int[n + 1];

        for(int i = 0; i < n; i++) {
            prefix_sum[i + 1] = prefix_sum[i] + array[i];
        }

    }

}

구간합

• 말 그대로 배열의 구간 내의 값을 다 더한 값이다.

코드

public class Main {

    public static void main(String[] args){
        int[] array = {1, 8, 7, 4, 3, 5, 6};
        int n = array.length;
        int[] prefix_sum = new int[n + 1];

        // 구간 1~5
        int x = 1;
        int y = 5;

        for(int i = 0; i < n; i++) {
            prefix_sum[i + 1] = prefix_sum[i] + array[i];
        }

        int part_sum = prefix_sum[y] - prefix_sum[x - 1];
    }

}

알고리즘 문제 추천

1. 수열 (실버 3)

• https://www.acmicpc.net/problem/2559

2. 구간 합 구하기 4 (실버 3)

• https://www.acmicpc.net/problem/11659

2차원 배열

누적합

• 2차원 배열은 행과 열로 이루어지며 1차원 배열보다 복잡하다.
• 2차원 배열에서는 가로 세로 0번째 인덱스는 이전 행과 열을 더해서 추가하면 쉽지만, 나머지 인덱스의 누적합은 현재 인덱스 기준으로 왼쪽, 왼쪽위, 위, 현재 까지 총 4가지의 값을 더한 값이 누적합이 된다.

코드

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        int size = matrix.length;

        int[][] prefix_sum = new int[size + 1][size + 1];

        for(int i = 1; i <= size; i++) {
            for(int j = 1; j <= size; j++) {
                // prefix_sum(i, j) = matrix(i, j) + prefix_sum(i - 1, j) + prefix_sum(i, j - 1) - prefix_sum(i - 1, j - 1)
                prefix_sum[i][j] = matrix[i - 1][j - 1] + prefix_sum[i-1][j] + prefix_sum[i][j-1]  - prefix_sum[i - 1][j - 1];
            }
        }

        Arrays.stream(prefix_sum).forEach(array -> System.out.println(Arrays.toString(array)));
    }

}

구간합

• 아래의 표에는 (x1,y1) 와 (x2,y2) 구간의 합을 표시한 것이다. 이 영역을 계산하려면, 공통 부분을 제거하면 된다.

• 아래 그림처럼 (x2,y2) 의 누적합에서 공통 부분인 (x2, y1-1), (x1-1,y2)를 빼주고, (x1-1, y1-1)를 더해주면 영역의 구간합이 계산된다.

코드

public class Main {

    public static void main(String[] args) {
        int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        int size = matrix.length;

        int[][] prefix_sum = new int[size + 1][size + 1];

        for(int i = 1; i <= size; i++) {
            for(int j = 1; j <= size; j++) {
                prefix_sum[i][j] = matrix[i - 1][j - 1] + prefix_sum[i-1][j] + prefix_sum[i][j-1]  - prefix_sum[i - 1][j - 1];
            }
        }

        int x1 = 2;
        int y1 = 1;
        int x2 = 4;
        int y2 = 3;

        int RangeValue = prefix_sum[x2][y2]  + prefix_sum[x1 -1][y1 -1] - prefix_sum[x2][y1 - 1] - prefix_sum[x1 - 1][y2];
    }

}

알고리즘 문제 추천

1. 구간 합 구하기 5 (실버 1)

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

참고 자료

https://jih3508.tistory.com/50