[JAVA][알고리즘] 구간 합

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 이다. 코딩 테스트에서 사용 빈도가 높기 때문에 알아두면 좋다.

 

구간 합은 누적합이라고도 하는데, C#으로 누적합을 정리해둔 글이 있으니 참고해도 좋을것 같다.

해당 게시글엔 2차원 배열의 누적합도 정리해 두었다.

[알고리즘] 누적합 (Prefix Sum)

---

구간 합 이론

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다.

 

배열 arr이 있을 때 합 배열 sumArr은 다음과 같다.

// arr[0] 부터 arr[i]까지의 합
SumArr[i] = arr[0] + arr[1] + arr[2] + ... + arr[i-1] + arr[i]

 

합 배열은 기존 배열을 이용해 만든 배열이다. 합 배열을 미리 구해 놓으면 기존 배열의 일정 범위 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소한다.

---

합 배열을 만드는 공식

sumArr[i] = sumArr[i-1] + arr[i]

// 배열 arr
int[] arr = {15, 13, 7, 23, 4, 11, 31, 10, 2, 19};

// 합 배열 만들기
sumArr[0] = arr[0];
for(int i = 1; i < arr.length; i++){
    sumArr[i] = sumArr[i-1] + arr[i];
}

이렇게 구현된 합 배열을 이용하여 구간 합을 쉽게 구할 수 있다. i에서 j까지 구간 합을 구하는 공식은 다음과 같다.

 

구간합을 구하는 공식

sumArr[j] - sumArr[i-1]

// 인덱스 2부터 4까지
sumArr[4]-sumArr[1]

 

이렇게 합 배열과 구간 합 공식을 사용하면 코딩 테스트에서 시간 복잡도를 줄이는데 도움이 된다.

---

합 배열을 만들고 구간합을 구하는 전체 코드

int[] arr = {15, 13, 7, 23, 4, 11, 31, 10, 2, 19};
int[] sumArr = new int[arr.length];

// 합 배열 만들기
sumArr[0] = arr[0];
for(int i = 1; i < arr.length; i++){
    sumArr[i] = sumArr[i-1] + arr[i];
}

// 인덱스 2부터 4까지
System.out.println(sumArr[4]-sumArr[1]);

# 출력 결과
34

---

관련 문제

[JAVA][백준][S1] 구간 합 구하기 5

[JAVA][백준][G3] 나머지 합

---

내용 출처

Do it! 알고리즘 코딩 테스트: 자바 편 | 김종관