개념
- 특정 배열이 있을 때, 구간의 합을 말한다.
- 예를 들어, 다음과 같은 배열이 있을 때 3번째부터 5번째까지의 누적합은 12이다.
구현
- 일반적으로 누적합을 구함에 있어, i번째부터 j번째까지의 누적합을 구하라고 할 때마다 하나씩 더하면 i~j까지를 m개의 원소라고 하면 시간 복잡도가 m(j-i+1)의 제곱으로 늘어난다.
- 하지만 간단한 개념을 도입하면 시간복잡도를 O(2)까지 줄일 수 있다.
- 전체 누적합을 구한다.
- i번째부터 j번째까지 누적합을 구하려면 전체 누적합의 j번째 인덱스에서 i-1번째 인덱스를 빼면 된다.
응용
자료구조 응용
세그먼트 트리
- 2042 구간 합 구하기
https://www.acmicpc.net/problem/2042
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
알고리즘 응용
투 포인터(이분탐색)과 함께한 응용
- 2559 수열
https://www.acmicpc.net/problem/2559 - 10986 나머지 합
2024.04.02 - [Algorithm/BaekJoon Review] - 10986. 나머지 합
2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
10986. 나머지 합
문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai +
l1m3kun.tistory.com
반응형
'Algorithm > 개념' 카테고리의 다른 글
| [알고리즘] 우선순위 큐와 힙(Priority Queue & Heap) (0) | 2024.03.12 |
|---|---|
| [자료구조] 큐(Queue) (0) | 2024.03.12 |
| [알고리즘] 문자열 - 트라이(Trie) (0) | 2024.02.04 |
| 크루스칼(Kruskal) - 최소 신장 트리(MST) (1) | 2024.01.10 |
| [알고리즘] Union-Find (1) | 2024.01.07 |