누적합 개념 정리
누적합: 배열에서 앞에서부터 해당 인덱스까지의 원소의 값을 모두 더한 것
구간합: i부터 j까지 해당 구간 사이 원소의 합
예를 들어 5 4 3 2 1 이라는 값을 가진 5 크기의 배열 arr가 있다고 하자.
1. 첫번째 누적합은 기존의 값이 그대로 내려온다.
2. 누적합과 그 다음 값을 더한 값이 두번째 누적합이 된다.
3. 위 과정을 반복해서 누적합 배열을 만든다.
만약 1~ 3번째 구간의 합을 구하고 싶다면 5+4+3=12 이므로 즉 인덱스 2번의 누적합 값이다.
2~4번째 구간의 합을 구하고 싶다면 4+3+2=9인데, 이 값은 1~4번째까지 더한 값 14에서 첫번째 값 5를 빼면 구할 수 있다.
정리하자면 i부터 j까지의 구간합은 j번째 누적합 - (i-1)번째 누적합이다.
누적합을 쓰는 이유
시간복잡도
수의 개수가 N인 배열에서 단순 반복문으로 계산할때의 최악의 경우 O(N^2)의 시간복잡도를 갖게 되는데
이를 누적합으로 계산하면 O(N) 상수시간으로 만들 수 있기 때문이다.
즉 시간을 훨씬 단축시킬 수 있기 때문에 누적합을 사용하는 것이다.
누적합에 대한 더 자세한 얘기는 백준 문제 풀이와 함께 볼 수 있다.
풀어보면 좋을 백준 문제
'알고리즘 자료구조 공부일지' 카테고리의 다른 글
| [알고리즘] 유니온 파인드 (Union-Find) 개념과 최적화 기법 (0) | 2024.04.28 |
|---|---|
| 시간복잡도(Time Complexity) (0) | 2024.04.17 |
| [알고리즘] 투포인터 (Two Pointer) (0) | 2023.08.12 |
| [알고리즘] 재귀함수 (Recursion Function) (0) | 2023.08.08 |
| 알고리즘의 개념과 배워야 하는 이유 (0) | 2023.08.08 |
