구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다.
🟡 합 배열 정의
S[i]는 A[0]부터 A[i]까지의 합
S[i] = A[0] + A[1] + ... A[i-1] + A[i]
S[i] = S[i-1] + A[i]
합 배열을 미리 정의해 놓으면 일정 구간의 합을 구하는 것의 시간복잡도를 줄여준다.
+) 합 배열 없이 일정 구간의 합을 구하는것은 시간 복잡도가 O(N)이고,
합 배열이 있으면 시간 복잡도가 O(1)이다.
🟡 구간 합 공식
i부터 j까지의 구간 합은
S[j] - S[i - 1]
'CS > 알고리즘' 카테고리의 다른 글
| [알고리즘] 브루트 포스(brute force) 알고리즘 (0) | 2023.01.16 |
|---|---|
| [알고리즘] 재귀(Recursion), 재귀 호출(Recursive call) (0) | 2023.01.02 |
| [알고리즘] 투 포인터, 슬라이딩 윈도우(two pointers, sliding window) (0) | 2022.12.14 |
| [알고리즘] 정렬 - 버블 정렬(bubble sort) (0) | 2022.11.28 |
| [알고리즘] 시간 복잡도(Time Complexity) (0) | 2022.10.20 |
댓글