[알고리즘] 구간 합

1. 개념

배열 A의 합 배열을 구해서 기존 배열의 일정 범위의 합을 구하는 방법

2. 합 배열

1) 개념

배열 A의 인덱스 0부터 인덱스 i까지 더한 값을 가지고 있는 배열

2) 공식

배열 A = {5, 4, 3, 2, 1}

 

S[1] = A[0]

S[2] = A[0] + A[1]

S[3] = A[0] + A[1] + A[2]

S[4] = A[0] + A[1] + A[2] + A[3] 

S[5] = A[0] + A[1] + A[2] + A[3] + A[4]

int[] A = {5, 4, 3, 2, 1};
int[] S = new int[A.length + 1] // 합 배열 index를 1부터 시작하는거라고 하기 위해 길이를 1 늘림

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

3. 구간 합 사용의 장점

• 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소함
  • 배열 A가 있다고 할 때, 합 배열 없이 A[i] 부터 A[j]까지의 합을 구한다고 하면 최악의 경우 i=0 부터 i=마지막까지 돌아야 하므로 O(N)이다. 하지만 합 배열이 있으면 S[j] - S[i-1] 한 번의 연산으로 값을 구할 수 있어서 O(1)의 시간복잡도가 된다

 

4. 구간 합 공식

배열 A의 두번째(i)부터 네번째(j)까지의 합을 구한다고 하자

A의 첫번째부터 네번째까지의 합인 S[4]에서 첫번째까지의 합인 S[1]을 빼면 두번째부터 네번째까지의 합이 나온다

S[j] - S[i-1]

5. 관련 문제

백준 11659번

GitHub - Lee-Min-Jung/coding_test_practice

백준 11660번

GitHub - Lee-Min-Jung/coding_test_practice

백준 10986