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

구간 합 배열은 우선 기존 제시되는 배열을 순차적으로 더해 나타내는 배열이다.
아래 배열이 기본적으로 주어져 있다.

int[] arr = { 1, 18, 21, 3, 6}

사이즈 5인 배열에 1, 18, 21, 3, 6 이 있고 이 배열을 기준으로 구간합 배열은 만들어준다.
S[i] = S[i - 1] + arr[i]
공식으로 만들어지고 만들어지는 코드는 아래와 같다.
(폰으로 적는 손코딩이라 돌려보지는 않은 코드입니다..ㅠ)

int[] arr_sum = new int[5]; 

// 인덱스 0 번째는 미리 arr 0번 인덱스로 초기화 
arr_sum[0] = arr[0];

for(int i = 1; i < are.length; i++){
   arr_sum[i] = arr_sum[i - 1] + arr[i];
}

그렇게 되면
arr_sum 변수에는 1, 19, 40, 43, 49 가 순서대로 담겨 있고 해당 함수로 구간 합을 구할수 있다.
인덱스 번호 기준 i ~ j 를 구할려면 공식은 아래와 같다.
s[j] - s[i - 1] 이고 실 데이터로 그린 내용은 아래와 같다.

(좀 휘날리는 부분 양해 부탁드립니다..ㅎ)

위와 같이 인덱스 4는 0 ~ 4 구간 합이고
2 ~ 4 는 (전체 - 2인덱스 전인 1) 와 같다.

구간합 배열은 코딩테스트에서도 자주 사용한다고 하였고 응용하는 방법은 코딩테스트 사용할때 공유 하겠다.