[알고리즘] 구간 합(백준 11659, 11660 -Java)

[알고리즘] 구간 합(백준 11659, 11660)

알고리즘 공부를 계속 미루는 제 자신을 보고 이대로는 안되겠다 싶어 😇
본격적으로 코딩테스트를 준비(+알고리즘 공부) 해보려고 합니다.
물론 혼자하면 작심삼일이 될거 같아
무료 Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의
강의 커리큘럼에 맞춰 공부해보자!!

[무료] Do it! 알고리즘 코딩테스트 with JAVA - 인프런 | 강의

 

자 모든 준비와 마음이 섰으니 기초부터 차근차근 공부해보자!

 

---

 

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 입니다.

합 배열이 뭔데??

방금 구간 합은 합 배열을 이용한다고 했습니다.
합 배열이란 무엇일까요?

// A[0] ~ A[i] 까지의 합
S[i] = A[0] + A[1] + ... + A[i-1] + A[i]
S[i-1] = A[0] + A[1] + ... A[i-1]

 

합 배열은 기존의 배열을 전처리한 배열이라고 생각하시면 됩니다.
이렇게 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하면 시간 복잡도가 O(n)에서 O(1)로 감소 합니다.

// 합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]

 

A[0] = 1, A[1] = 2, A[2] = 3, A[3] = 4, A[4] = 5
일때 S[4]의 값은?

// 합 배열을 이용하여 구하기
S[0] = A[0] = 1
S[1] = S[0] + A[1] = 1 + 2 = 3
S[2] = S[1] + A[2] = 3 + 3 = 6
S[3] = S[2] + A[3] = 6 + 4 = 10
S[4] = S[3] + A[4] = 10 + 5 = 15

구간 합

합 배열을 이용하여 구간 합을 쉽게 구할 수 있습니다.

// 구간 합 구하는 공식
// i에서 j까지 구간 합 (단, i > 1)
S[j] - S[i-1] 

그림으로 보면 이해가 쉬울 것 입니다.^^

하나의 배열 안에서 구간 합에 대한 질문이 많은 케이스인 경우에 합 배열을 사용하면 좋을 것으로 보입니다.
왜냐하면! 합 배열만 미리 구해 두면 구간 합은 한 번의 계산으로 구할 수 있기 때문이죠.

 

합 배열을 잘 이용하면 코딩테스트에서 시간 복잡도를 줄이는데 많은 도움이 될 것으로 보입니다.^^

 

그런데 다음과 같은 경우에는 문제가 발생합니다.

S[-1]이라는 값은 존재하지 않습니다.
공식만으로는 해결이 안될거 같아요…. 😭
어떻게 문제를 해결해야 할까요?

 

합 배열의 크기를 하나 증가하고, index 0에 0을 넣어 초기화 합니다.

// 구간 합 구하는 공식
// 배열 A의 index i에서 j까지 구간 합(단, i >= 0)
S[j+1] - S[i]

 

만약 배열의 값이 자주 바뀌면 어떻게 하지?
이럴 경우에 사용하는것이 바로 세그먼트 트리를 사용 하면 됩니다.
세그먼트 트리는 다른 포스팅에서 다루겠습니다.

백준 11659

11659번: 구간 합 구하기 4
푸는데 50분정도 걸렸다… ㅠ0ㅠ
마지막 구간 합 결과를 반환하는 함수에서 시간이 많이 소요되었다.

11659번: 구간 합 구하기 4

문제에서 수의 갯수와 합을 구해야 하는 횟수는 100,000입니다.
(Java 에서 1억개의 loop를 처리하는데 1초 정도 걸린다고 합니다.)
배열의 합을 계속 구하면서 합을 계산하면 시간 제한안에 프로그램이 동작하지 못할 가능성이 큽니다.
따라서 반드시 구간 합을 사용해서 문제를 풀어야 합니다.

 

풀이
질의는 1부터 시작하고, index는 0부터 시작합니다.
그래서 구간 합 배열의 0번째 index에 0을 저장하고 1부터 시작하도록 작성했습니다.

 

 

S[0] = 0
// 배열 A의 index i에서 j까지의 합(단, i >= 0)
S[j+1] - S[i]

 

public class Quiz11659 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        // 배열 갯수
        int n = Integer.parseInt(st1.nextToken());
        // 질의 횟수
        int m = Integer.parseInt(st1.nextToken());

        // 배열 저장
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] nNum = new int[n];
        for(int i = 0; i < n; i++) {
            nNum[i] = Integer.parseInt(st2.nextToken());
        }

        // 합 배열 계산
        int[] rangeSum = getRangeSum(n, nNum);

        // 구간 저장
        int[][] range = new int[m][2];
        for(int i = 0; i < m; i++) {
            StringTokenizer st3 = new StringTokenizer(br.readLine());
            for(int j = 0; j < 2; j++) {
                range[i][j] = Integer.parseInt(st3.nextToken());
            }
        }

        // 결과
        for(int k = 0; k < m; k++) {
            System.out.println(getResult(range, rangeSum, k));
        }
    }

    // 구간 합 결과
    private static int getResult(int[][] range, int[] rangeSum, int k) {
        /**
         * 배열 A의 index i에서 j까지의 합
         * S[j+1] - S[i]
         */
        int i = range[k][0] - 1;
        int j = range[k][1] - 1;

        return rangeSum[j+1] - rangeSum[i];
    }

    // 합 배열 계산
    private static int[] getRangeSum(int n, int[] nNum) {
        int[] rangeSum = new int[n+1];
        int numSum = 0;
        rangeSum[0] = 0; // index = 0에는 0을 넣어준다.
        for(int i = 0; i < n; i++) {
            numSum += nNum[i];
            rangeSum[i+1] += numSum;
        }
        return rangeSum;
    }
}

 

 

풀이2
합 배열을 입력과 동시에 구하고, 기존 공식을 사용하는 방법도 있습니다.
풀이1에서는 index로 구간을 생각했습니다.
이번에는 질의의 구간 그대로 사용해서 코드를 작성해 보겠습니다.

// 구간 합 구하는 공식
// i에서 j까지 구간 합(단, i >= 1)
S[j] - S[i-1]

 

public class Quiz11659 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        // 배열 갯수
        int n = Integer.parseInt(st1.nextToken());
        // 질의 횟수
        int m = Integer.parseInt(st1.nextToken());

        // 합 배열 계산
        int[] rangeSum = getRangeSum(br, n);

        // 구간 저장
        int[][] range = new int[m][2];
        for(int i = 0; i < m; i++) {
            StringTokenizer st3 = new StringTokenizer(br.readLine());
            for(int j = 0; j < 2; j++) {
                range[i][j] = Integer.parseInt(st3.nextToken());
            }
        }

        // 결과
        for(int k = 0; k < m; k++) {
            System.out.println(getResult(range, rangeSum, k));
        }
    }

    // 합 배열 계산
    private static int[] getRangeSum(BufferedReader br, int n) throws IOException {
        // 입력과 동시에 합 배열 계산
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] rangeSum = new int[n +1];
        for(int i = 0; i < n; i++) {
            rangeSum[i+1] = rangeSum[i] + Integer.parseInt(st2.nextToken());
        }
        return rangeSum;
    }

    // 구간 합 결과
    private static int getResult(int[][] range, int[] rangeSum, int k) {
        /**
         * 배열 i ~ j 까지 구간 합
         * S[j] - S[i-1]
         */
        int i = range[k][0];
        int j = range[k][1];

        return rangeSum[j] - rangeSum[i-1];
    }
}

백준 11660

11660번: 구간 합 구하기 5

11660번: 구간 합 구하기 5

 

내 힘으로 풀지 못했다..😭
참고: Java / 백준 11660 구간 합 구하기 5
위 블로그를 참조하여 문제를 해결했습니다.

[Java / 백준 11660] 구간 합 구하기 5

 

2차원 배열의 합 배열을 만들고, 구간 합을 계산하는것이 어려웠다.

 

2차원 배열 합 배열 만들기

먼저 주어진 배열로 부터 합 배열을 구해야 합니다.
1행의 누적 합과 1열의 누적 합을 계산하면 아래 그림과 같습니다.

합 배열(S) 2행 2열은 어떻게 계산해야 할까요?🤔

 

합 배열(S) 2행 2열 ?
배열 A를 보면 이해하기가 쉽습니다.

S[2][2] = ?

= (A[0][0] + A[0][1]) 
    + (A[0][0] + A[1][0]) 
    + A[1][1] 
    - S[1][1]

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

 

 

 

 

합 배열(S) 2행 3열 ?

 

합 배열(S) 2행 4열 ?

 

구간 합 배열 계산

이제 구간 합을 구해야 합니다.

 

수식으로 변경합니다.

 

풀이

public class Quiz11660 {
    public static void main(String[] args) throws IOException {

        // 1. n, m 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());    // 2차원 배열의 크기
        int m = Integer.parseInt(st.nextToken());    // 구해야하는 구간 합의 수

        // 2. 2차원 합 배열 구하기
        int[][] sumArr = new int[n+1][n+1];
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= n; j++) {
                sumArr[i][j] = sumArr[i-1][j] + sumArr[i][j-1] + Integer.parseInt(st.nextToken()) - sumArr[i-1][j-1];
            }
        }

        // 3. 구간 합 계산
        for(int i = 0; i < m; i++) {
            /**
             * (i, j) 구간 합
             * S[j] - S[i-1]
             *
             *
             * (x1, y1) (x2, y2) 까지 합
             * S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]
             */
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());

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