Prefix Sum (수열의 구간 합 구하기)

나열된 수열의 개수 n개

몇번 범위 합을 구해 볼지의 개수 m개

범위 지정 시작 start, 끝 end를 이용하여 수열의 범위의 합을 구하는 알고리즘이다.

즉, 

n = 6, m = 2이면

2 3 5 4 1 3 의 수열을 만들고 (n에 의해)

1 3 (start = 1, end = 3)

2 5 라는 두개의 범위를 만든다. (m에 의해) (start = 2, end = 5)

그러면 출력되는 합은

10

13 이 출력된다.

#include <stdio.h>
 
 int i,j,n,m,start,end,sum = 0;
 int a[100005];
 
int main()
{ 
 scanf("%d %d",&n,&m);
 
 for(i = 0; i < n ; i ++) scanf("%d",&a[i]); // 길이만큼 숫자 입력 
 
 for(i = 0; i < m ; i ++) // 몇번째부터 몇번째까지 더할지  
 {
  scanf("%d %d",&start,&end);
  
  for(j = start-1 ; j <= end-1 ; j++)
  {
   sum = sum + a[j];   
  }
  printf("%d\n",sum);
  sum = 0; 
 }
 
    
   return 0; 
}
 

위의 알고리즘과 아래의 알고리즘은 둘다 수열의 합을 구하는 알고리즘이다.

하지만 위의 알고리즘은 n,m,start,end의 값이 커질수록 계산해야되는 양이 n*m이 되어 최악의 경우의수를 가져올 수 있다.

2중 for문에 의한 커지는 경우의 수이다.

하지만 아래 코드는

2중 for문의 내용을 분해해서 단일 for문으로 만들었기에

n+m의 경우의 수를 가져온다.

많은 경우 위의 알고리즘 처럼 구상하지만, 값이 커질때는 아래의 알고리즘 (Prefix Sum)이 있다는 것을 알고 있으면 좋다.

(물론 위의 알고리즘은 적당한 값일 경우 이용하여도 무방하다.)

 
#include <stdio.h>
int main()
{ 
 int i,n,m,start,end, ans;
 int a[100000]; // 값을 받는 배열 
 int sum[100000]; // a[0]~a[n]까지 합을 넣어두는 배열 
 scanf("%d %d",&n,&m);
 
 for(i = 0; i < n ; i++) 
 {
     scanf("%d",&a[i]); // 길이만큼 숫자 입력 
     if (i == 0)
         sum[i] = a[i]; 
     else
         sum[i] = sum[i-1] + a[i]; // a[0]부터 a[i-1]의 합을 넣어둔다. 
 }
 for(i = 0; i < m ; i++) // 몇번째부터 몇번째까지 더할지  
 {
  scanf("%d %d",&start,&end);
  if (start == 1)
      ans = sum[end-1]; 
  else
      ans = sum[end-1] - sum[start-2];  // 예를들면 S4 - S3은 a4 같은 알고리즘을 이용한다. 
  printf("%d\n",ans);
 }
 
  return 0; 
}