[240301] 알고리즘 리부트 21일차 - 백준 11659, 11660, 19951 자바

[Part1-Chapter06-Clip01]

구간 합 계산 시 누적합 배열을 활용한다면 해당 인덱스로 접근하여 한 번에 연산이 가능하기 때문에 시간 복잡도가 현저히 낮아진다. 해당 특정 배열의 원소가 갱신된다면 해당 원소의 인덱스부터 그 이후 모든 누적합 원소에 수정이 필요하기 때문에 배열의 길이인 N만큼 순회해야 하므로 시간 복잡도는 O(N) 이다. 만약 갱신하는 것을 반영해 구간합을 구한다면 누적합 배열을 사용한다 하더라도 시간 복잡도가 크게 낮아지지 않는다는 것을 알 수 있다.

- 백준 11659 구간 합 구하기 4

한 달 전에도 풀었던 문제인데 시간 초과 때문에 Scanner 대신에 BufferedReader와 StringTokenizer를 사용했고 String 대신 StringBuilder를 사용했다. 입력을 받을 때부터 구간 합을 구하며 각 요소는 첫 요소부터 해당 요소까지의 합이 되게 한다. 배열을 채우고 구간의 시작점과 끝점을 주기 때문에 끝점에서 시작점 바로 이전 인덱스의 값을 뺀다면 해당 구간의 합을 구할 수 있다. 

package BaekJoon.prefixSum;

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] prefixSum = new int[n + 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + Integer.parseInt(st.nextToken());
        }

        //System.out.println(Arrays.toString(prefixSum));

        StringBuilder sb = new StringBuilder();


        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            sb.append(prefixSum[end] - prefixSum[start - 1] + "\n");
        }

        System.out.println(sb);

    }
}

 

[Part1-Chapter06-Clip03]

-백준 11660 구간 합 구하기 5

아래는 오늘 내가 배열을 열댓번 그려가면 푼 코드이다. 주어진 테스트 케이스를 보면서 이리 저리 봐도 행과 열을 모두 대각선 방향에 반영하려면 중복이 일어날 수밖에 없었고 그래서 좌상 대각선의 값을 빼는 방식으로 처리함으로써 누적합을 구현했다. 복잡하게 누적합을 구현한 만큼 구간합을 구하는 복원 로직이 복잡했다. 하.. 한참 고민해서 풀어냈고 그 결과 메모리나 시간은 훨씬 적게 소요되었다.

package BaekJoon.prefixSum;

import java.io.*;
import java.util.StringTokenizer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = 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++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] acc = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                acc[i][j] = acc[i][j - 1] + acc[i - 1][j] - acc[i - 1][j - 1] + arr[i][j];
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while (m-- > 0) {
            int ans = 0;
            st = new StringTokenizer(br.readLine());
            int sx = Integer.parseInt(st.nextToken());
            int sy = Integer.parseInt(st.nextToken());
            int ex = Integer.parseInt(st.nextToken());
            int ey = Integer.parseInt(st.nextToken());

            ans = acc[ex][ey] - (acc[ex][sy - 1] + acc[sx - 1][ey]) + acc[sx - 1][sy - 1];

            //System.out.println(ans);

            bw.write(ans + "\n");
        }

        br.close();
        bw.flush();

    }
}

푸는 과정에서 중복을 줄이기 위해 행만 더한 배열과 열만 더한 배열을 고민하기도 했으나 이를 구간합에 어떻게 처리할지까지는 생각하지 못하고 포기했다..  하지만 이전에 풀이한 코드를 보니 웬걸 열만 더해서 구간합을 만든 것이었다. 도대체 나는 저런 코드를 어떻게 생각했었을까. 지금은 행만, 열만 더하는 배열을 생각하고 시도했던 것에 그쳤는데 말이다. 문제를 푸는 방식은 다양하니 푸는 방식을 하나 더 배웠다고 생각하자. 

아래 코드는 배열을 입력받는 과정에서 열 기준으로만 누적합 배열을 만들었고, 특정 구간의 합을 구할 때는 해당되는 행의 구간에서만 끝열의 값에서 시작열의 직전 열 값을 뺌으로써 구간합을 구할 수 있다. 제한된 시간과 메모리 내에서 처리할 수 있다면 굳이 열과 행을 모두 반영한 배열은 필요 없는 것이었다. 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        int[][] table = new int[m+1][m+1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= m; j++) {
                table[i][j] = table[i][j-1]+sc.nextInt();
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {

            int sum = 0;
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();

            for(int j = x1; j<=x2; j++){
                sum= sum+(table[j][y2]-table[j][y1-1]);
            }
            sb.append(sum).append("\n");
        }
        System.out.println(sb.toString());
    }
}

 

[Part1-Chapter06-Clip03]

- 백준 19951 태상이의 훈련소 생활

최대 연산 횟수가 100억번 이기에..  당연히 O(n*m)의 시간복잡도 때문에 시간 초과 날 것이라고 생각했다. 그런데 누적합 배열 문제라는 사실을 아는데도 도무지 풀이 방법이 떠오르지 않아 참고하여 풀었다. 중요한 건 m 안에서 n 번 반복하지 않게 하는 것이기에 m 안에서 결단을 봐야한다고 생각은 했었다..^^;; 

지시의 시작 칸과 끝 칸 그리고 높이를 가지고 누적합을 위한 구분자를 먼저 넣어주고 즉, 시작점에는 높이 값, 끝점 +1 칸에는 이를 해제하는 -높이 값을 넣어준다. 이후에 해당 칸을 1회 반복 돌면서 누적합을 만들어준다. 이렇게 하면 해당 구간에만 누적되고 구간을 벗어나서는 적용되지 않는다. 

package BaekJoon.prefixSum;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] ground = new int[n + 2];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            ground[i] = Integer.parseInt(st.nextToken());
        }

        int[] work = new int[n + 2]; // 누적합 때문에 연산이 복원되는 마지막 원소를 위한 자리

        while (m-- > 0) { // 누적합 적용 위한 구분자 처리
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int height = Integer.parseInt(st.nextToken());

            work[start] += height;
            work[end + 1] += (-height); // 누적합 중지시키기 위한 복원 처리

//            System.out.println("work[" + start + "]: " + work[start]);
//            System.out.println("work[" + (end + 1) + "]: " + work[end + 1]);
        }

        for (int i = 1; i <= n + 1; i++) {
            work[i] = work[i] + work[i - 1];
//            System.out.println("work[" + (i - 1) + "]: " + work[i - 1]);
//            System.out.println("work[" + (i) + "]: " + work[i]);
        }

        //System.out.println(Arrays.toString(work));

        br.close();

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (int i = 1; i <= n; i++) {
            ground[i] += work[i];
            bw.write(ground[i] + " ");
        }

        bw.flush();


    }
}