[알고리즘] 구간 합

1. 구간 합이란

• 합 배열을 이용, 시간복잡도를 줄이는 특수한 목적으로 사용되는 알고리즘이다.

2. 합 배열의 정의

• 합 배열이란, 기존 배열의 합을 미리 구해놓는 전처리 배열이다.
• 합 배열을 미리 구해놓으면 구간합을 구할 때의 시간복잡도가 O(n)에서 O(1)로 줄어든다.

  sum[i] = a[0] + a[1] + ... + a[i - 1] + a[i]

  public static void main(String[] args) {
    int[] a = {15, 13, 10, 7, 3, 12};
    int[] preSum = new int[a.length];
    for (int i = 0; i < a.length; i++) {
        if(i == 0) preSum[i] += a[i];
        else preSum[i] = preSum[i - 1] + a[i];
    }
  }

3. 구간합 구하기

• 위에서 본 코드를 바탕으로 a[2] ~ a[5]의 구간합은 어떻게 구할까?
• 구간합을 구하는 공식

  sum[j] - sum[i - 1] // i에서 j까지의 구간 합

  -> preSum[5] - preSum[1]을 해주면 간단하게 구할 수 있다.
  • preSum[5] = a[0] ~ a[5]의 합이고
  • preSum[1] = a[0] + a[1]이기 때문에 preSum[5]에서 preSum[1]을 빼주면 a[2]에서 a[4]까지의 합만 남게 된다.

 

 

백준 [구간 합] - 11659 구간 합 구하기4