자바 JAVA | 백준 11659번 구간 합 구하기 4 | 부분 합을 이용한 구간 합 구하기 알고리즘

 

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

11659번: 구간 합 구하기 4

 

✅ 문제

• 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.
• 시간제한: 1초
• 메모리 제한: 256 MB

 

💡 입력

• 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 
• 둘째 줄에는 N개의 수가 주어진다. 
• 수는 1,000보다 작거나 같은 자연수이다. 
• 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

💡 출력

• 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

💡 제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

 

💡 예제 입력 1

5 3
5 4 3 2 1
1 3
2 4
5 5

 

💡 예제 출력 1

12
9
1

 

✅ 해결

💡 해결 계획

1. 구간 합 배열을 구한다. 
2. 구간 합을 구하는 질문에 대해서는 구간 합 배열을 이용하여 O(1) 시간 안에 구한다.

 

💡 코드 1 (실패)

시간 복잡도는 O(NM)이다. 

• N은 배열의 크기이며, M은 구간 합을 구하는 횟수이다. 
• M개의 구간에 대해 배열을 탐색하므로 시간 복잡도는 O(NM)이다. 

 

다음 코드가 실패하는 이유이다.

• 입력 범위 초과
  • 입력값의 범위를 제한하지 않았다.
  • 입력값이 너무 크면 메모리 초과나 시간 초과가 발생한다.
• 구간 합 계산 방법
  • 구간 합을 구하는 방법은 누적 합을 이용하는 것이 가장 효율적이다.
  • 구간 합을 구할 때마다 배열을 탐색하며 합을 계산한다.
  • 배열이 매우 커지거나 구간의 개수가 많아질수록 계산 시간이 증가하므로 비효율적이다.
• 불필요한 반복문
  
  • 누적 합을 이용하지 않고 매번 배열을 탐색하여 합을 계산한다.
  • 불필요한 반복문이 많이 실행되어 시간 복잡도가 증가한다.

 

다음 사항 개선하여 구간 합을 더 빠르게 구한다.

• 누적 합: 배열의 값을 모두 더해 누적한 값을 저장하고 각 구간 합을 누적 합을 이용한다.
• 세그먼트 트리: 트리 구조를 이용하여 배열의 구간 합을 빠르게 계산한다.
• 입력값의 범위를 제한하고, 불필요한 반복문을 줄인다.

 

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // n의 값 입력
		int m = sc.nextInt(); // m의 값 입력

		int[] arr = new int[n]; // 크기 n의 숫자 배열 선언
		for (int i = 0; i < n; i++) { // 크기 n의 배열에 각 숫자 입력
			arr[i] = sc.nextInt();
		}

		int sum = 0;
		for (int i = 0; i < m; i++) { // m번 구간 합을 구하기 위한 반복문
			sum = 0;
			int a = sc.nextInt(); // 구간 합을 구할 구간의 시작점 입력
			int b = sc.nextInt(); // 구간 합을 구할 구간의 끝점 입력
			for (int j = a - 1; j < b; j++) { // 시작점부터 끝점까지 합을 구하기 위한 반복문
				sum += arr[j];
			}
			System.out.println(sum); // 구간 합 출력
		}
	}
}

 

💡 코드 2 (성공)

시간 복잡도는 O(N + M)이다.

• N은 입력값으로 주어지는 숫자의 개수이며, M은 구간의 개수이다.
• N번의 루프를 돌며 각각의 숫자를 배열에 저장하면서 누적 합을 계산하므로 시간 복잡도는 O(N)이다.
• M번의 루프를 돌며 구간의 시작과 끝 인덱스를 입력받아 해당 구간의 합을 계산하므로 시간 복잡도는 O(M)이다.

 

부분 합으로 구간 합을 구한다.

1. 입력 값을 받고 배열을 생성한다.
2. 배열의 각 인덱스까지의 합을 저장하는 배열(부분 합 배열)을 생성한다.
3. 각 구간의 합을 구할 때는 부분 합 배열에서 구간의 끝 인덱스와 시작 인덱스를 이용한다.
4. 구간의 합을 구할 때는 부분 합 배열에서 끝 인덱스의 값에서 시작 인덱스 - 1의 값의 차를 구한다.

 

import java.util.Scanner;

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

        int n = sc.nextInt(); // n의 값 입력
        int m = sc.nextInt(); // m의 값 입력

        int[] arr = new int[n + 1]; // 부분 합을 저장할 배열 생성
        arr[0] = 0; // 0번째 인덱스는 0으로 초기화
        for (int i = 0; i < n; i++) {
            arr[i + 1] = arr[i] + sc.nextInt(); // 합으로 배열 생성
        }

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(); // a의 값 입력
            int b = sc.nextInt(); // b의 값 입력
            System.out.println(arr[b] - arr[a - 1]); // 부분 합을 이용하여 구간 합 출력
        }
    }
}

 

✅ 개념

💡 부분 합 Prefix Sum

배열의 각 원소에 대해 그 원소까지의 합을 미리 구해놓은 것이다.

배열의 첫 번째 원소부터 마지막 원소까지 각 원소에 대해 합을 구하는 과정을 미리 수행한다.

 

• 배열 {2, 4, 1, 7, 3}
• 배열의 부분 합 {0, 2, 6, 7, 14, 17}
• 부분 합 배열의 i번째 원소는 원래 배열의 0번째 원소부터 i번째 원소까지의 합이다.
• 부분 합을 이용할 때 배열의 첫 번째 원소를 0으로 초기화한다.

 

구간 합은 배열의 특정 구간에 속한 원소들의 합이다.

부분 합을 이용하여 구간 합을 빠르게 구한다.

부분 합을 이용하면 구간 합을 시간 복잡도는 O(1)이다.

 

• 구간 합을 계산할 때 b번째 원소까지의 합에서 a-1번째 원소까지의 합을 뺀다.

 

int[] arr = {2, 4, 1, 7, 3}; // 예시 배열

int[] psum = new int[arr.length]; // 부분 합을 저장할 배열 생성
psum[0] = arr[0]; // 0번째 인덱스는 원래 배열의 첫 번째 원소와 같다.

// 부분 합을 계산하여 배열에 저장
for (int i = 1; i < arr.length; i++) {
    psum[i] = psum[i-1] + arr[i];
}

// 부분 합 배열 출력
for (int i = 0; i < psum.length; i++) {
    System.out.print(psum[i] + " ");
}

 

부분 합을 이용하여 부분 곱(Prefix Product)을 구한다.

• 부분 합을 이용할 때 배열의 첫 번째 원소를 1로 초기화한다.