* 구간합 (Prefix Sum)
합 배열을 이용해서 시간 복잡도를 줄임
합 배열 (Prefix Sum Array)
첫 원소부터 해당 index까지의 합
prefixSum[i] = prefixSum[i-1] + arr[i]
index 오류를 방지하기 위해서
prefixSum[N+1] 등으로 설정하고
반복문 등에서 index를 1부터 시작, N까지로 설정할 수 있다
(이 경우 subSum[0] = 0 설정)
..~~~~..
* 합 배열을 이용한 구간 합 구하기
구간 n1~n2의 합 = prefixSum[n2] - prefixSum[n1-1]
..~~~~..
그동안 난 prefixSum가 아니라 subSum으로 사용하고 있었다..
..~~~~..
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 분할 & 정복 (Divide and Conquer) (0) | 2025.05.03 |
|---|---|
| 모듈러 연산의 성질 (Modular Arithmetic Property) (0) | 2025.05.02 |
| 동적 프로그래밍 (DP, Dynamic Programming) (0) | 2025.04.29 |
| 유클리드 호제법 (Euclidean Algorithm) (0) | 2025.04.17 |
| 에라토스테네스의 체 (Sieve of Eratosthenes) (0) | 2025.04.17 |