[CH01] 구간합

Algorithm || DataStructure

#01. 구간합

Date : 2022/09/09

틀린 내용이 있을 시, 지적해주시면 감사하겠습니다!

---

1. 배열과 리스트

배열의 특징

• 인덱스를 사용해서 원소에 O(1) 에 접근 가능
• 새로운 값 삽입 및 특정 위치의 값 삭제가 비효율적. (땡기거나 밀어줘야함)
• 선언할 때 한번 지정한 배열의 크기는 늘리거나 줄일 수 없다.

리스트의 특징

• 값에 접근하려면 O(N) 이 필요함.
• 데이터의 삽입 삭제가 O(1) 에 가능
• 가변 길이임

예제 : 숫자의 합

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

11720번: 숫자의 합

숫자를 String 으로 입력받은 다음, 각각의 원소를 누적하여 더해서 출력해주면 된다.

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        String number = sc.next();
        int ans = 0;

        for(int i = 0 ; i < t ; i++){
            ans += (number.charAt(i)-'0');
        }
        System.out.println(ans);
    }
}

예제 : 평균 구하기

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

1546번: 평균

각각의 점수를 배열에 저장한 뒤 문제에서 주어진 대로 평균을 계산하면 된다.

import java.util.Scanner;

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

        for(int i = 0 ; i < tc; i++){
            arr[i] = sc.nextInt();
        }
        long max = 0;
        double avg = 0.0;
        long sum = 0;

        for(int i = 0 ; i < tc; i ++){
            if(max < arr[i]) max = arr[i];
            sum += arr[i];
        }

        avg = ((sum*100.0)/max)/tc;
        System.out.println(avg);
    }
}

 

2. 구간 합

  합 배열을 이용해서 시간 복잡도를 줄이기 위해 사용하는 알고리즘이다. 먼저 배열 A 에 대한 합 배열 S 를 정의해야 한다. 합배열은 S[i] = A[0] + A[1] + A[2] ... + A[i-1] + A[i] 와 같이 정의한다. S 를 정의함으로 써, 기존 배열 A 에서 range sum 을 구해야 하는 경우 O(N) -> O(1) 으로 최적화할 수 있다. 

 

  A[2]~A[4] 간의 구간합을 구하려면 S[4]-S[1] 을 계산하면 되고 이는 15-8 = 7 이다.

 

예제 : 구간 합 구하기

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

11659번: 구간 합 구하기 4

  수의 개수는 최대 100,000 이고 합을 구해야 하는 횟수의 최대는 100,000 이니 최악의 경우 100,000 * 100,000 = 10,000,000,000 으로 1억 이상의 연산이 필요하므로 제한 시간인 1초 내에 절대로 결과를 낼 수 없다. 이러한 경우에 구간합 알고리즘을 이용해서 최적화를 하면 O(M) 에 해결할 수 있다.

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int tc = sc.nextInt(); // testcase

        int[] arr = new int[n+1];
        int[] s = new int[n+1];

        for(int i = 1 ; i <= n ; i++){
            arr[i] = sc.nextInt();
        }

        s[1] = arr[1];
        for(int i = 2; i<=n; i++){
            s[i] = s[i-1] + arr[i];
        }

        for(int i = 0 ; i < tc; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            int range_sum = s[end] - s[start-1];
            System.out.println(range_sum);
        }
    }
}

예제 : 구간 합 구하기 2

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

11660번: 구간 합 구하기 5

2차원 배열에서 누적합을 수행하는 문제이다. 핵심 아이디어는,

dp[x][y] = dp[x-1][y] + dp[x][y-1] - dp[x][y-1] + dp[x-1][y-1] 인 것이고

(x1, y1) ~ (x2, y2) 까지의 합 ans = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1] 라는 것이다. 

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

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

        int size = Integer.parseInt(st.nextToken());
        int tc = Integer.parseInt(st.nextToken());

        int[][] arr = new int[size+1][size+1];
        int[][] dp = new int[size+1][size+1];

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

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

        for(int i = 0 ; i < tc; i++){
            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());
            // (x1, y1) ~ (x2, y2)
            int ans = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
            System.out.println(ans);
        }
    }
}

예제 : 나머지합

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

10986번: 나머지 합

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

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 숫자 개수
        int m = Integer.parseInt(st.nextToken());

        long ans = 0;
        long[] s = new long[n];
        long[] r = new long[m];

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

        for(int i = 0 ; i < n ;i++){
            int rem = (int)(s[i]%m);
            if(rem == 0) ans++;
            r[rem]++;
        }

        for(int i = 0 ; i < m ;i++){
            if(r[i]>0){
                ans+=(r[i]*(r[i]-1))/2;
            }
        }
        System.out.println(ans);
    }
}

 

---

References

1. http://www.yes24.com/Product/Goods/108571508

Do it! 알고리즘 코딩 테스트 자바 편 - YES24