[알고리즘] 구간합/ 합배열

*알고리즘: 문제 해결을 위한 절차

1.어떤 문제? 
2.어떤 절차? ㅡ>Pseudo Code
3.어떻게 구현? ㅡ> Java
------------------------------------------------

1.어떤 문제를 해결하기 위한 알고리즘인지

구간합을 구하는 문제에서 시간복잡도를 줄이기 위해 합배열을 이용한다. 원본 배열에서 i인덱스에서 j인덱스까지의 합을 구한다고 할 때 (i <= j)  반복문을 이용하면 시간복잡도는 O(n)이 된다. 합배열의 i번 인덱스는 원본배열의 0번인덱스부터 i번 인덱스까지 요소의 합이다. 0~i번 인덱스까지의 합, 또는 i~j번 인덱스까지의 합을 구하기 위해 반복문을 사용하지 않고도 인덱스를 이용하여 값을 구할 수 있기 때문에 시간복잡도는 O(1)으로 줄어든다.

2.알고리즘의 절차

1.원본 배열에 대한 합 배열 S를 만든다.
  1) 원본 배열의 길이만큼 합 배열 S를 선언한다.
    (*합배열의 길이를 원본배열 +1로 만들어 1번 인덱스 부터 세팅하는 방법도 있다.)
  2) 합배열의 0번 인덱스에 원본 배열의 0번 인덱스 요소를 넣는다.
  3) 반복한다. ( index => 1 ~ 배열의길이-1) 
    합배열 S의 index번째의 값을 합배열 S의 index-1번째 + 원본배열의 index번째로 할당한다.

2. 합배열을 이용하여 문제에서 원하는 구간합을 계산한다.
   -원본 배열의 index번째까지의 합은 S[index]
   -원본 배열의 i~j번째 인덱스까지의 합은 S[j] - S[i-1]

3.Java 구현

int[] S = new int[arr.length];
S[0] = arr[0];
for(int i=1; i<arr.length; i++){
  S[i] = S[i-1] + arr[i];
}

//arr의 i번 인덱스까지의 합은 S[i]
//arr의 i~j번째 인덱스까지의 합은 S[j] - S[i-1]