✔ 구간 합
구간 합이란?
- 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
- 합 배열 없이 구간 합을 구할 경우, 시간 복잡도는 O(N)
- 합 배열을 사용할 경우, 시간 복잡도는 O(1)
합 배열 S 정의
- S[i] = A[0] + A[1] + A[2] + ... + A[i - 1] + A[i]
합 배열 S를 만드는 공식
- S[i] = S[i - 1] + A[i]
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
| 배열 A | 3 | 6 | 5 | 10 | 4 |
| 합 배열 S | 3 | 9 (3 + 6) | 14 (9 + 5) | 24 (14 + 10) | 28 (24 + 4) |
구간 합을 구하는 공식
- 구현된 합 배열을 이용하면 한 번의 계산으로 구간 합을 쉽게 구할 수 있음
- i에서 j까지의 구간 합 = S[j] - S[i - 1]
더보기
Do it! 알고리즘 코딩테스트 with JAVA
'Coding Test > 알고리즘 개념' 카테고리의 다른 글
| [자료구조] 슬라이딩 윈도우 (0) | 2023.06.28 |
|---|---|
| [자료구조] 투 포인터 (0) | 2023.06.28 |
| [자료구조] 배열과 리스트 (0) | 2023.06.27 |
| [코딩 테스트 준비하기] 디버깅 (0) | 2023.06.26 |
| [코딩 테스트 준비하기] 시간 복잡도 (0) | 2023.06.26 |
