728x90
구간 합
합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘이다.
합 배열이란, 0부터 인데스(i)까지의 합으로 이루어진 배열을 의미한다.
합 배열을 미리 구해놓으면, 기존 리스트의 특정 범위의 합을 구하는 시간 복잡도를 O(n)에서 O(1)로 감소시킬 수 있다.
리스트 A의 합 배열을 S라고 가정하자.
A = [15, 13, 10, 7, 3, 12]
S = [15, 28, 38, 45, 48, 60] (S[i] = S[i-1] + A[i])
인덱스 i에서 j까지의 구간 합 구하기: S[ j ] - S[ i - 1 ]
728x90
'알고리즘' 카테고리의 다른 글
| 정렬: 버블 정렬/선택 정렬/삽입 정렬/퀵 정렬/병합 정렬/기수 정렬 (1) | 2024.01.05 |
|---|---|
| 자료구조(3): 투 포인터, 슬라이딩 윈도우, 스택과 큐 (2) | 2024.01.04 |
| 자료구조(1): 배열과 리스트 (1) | 2024.01.03 |
| 알고리즘의 기본, 시간 복잡도 (1) | 2024.01.03 |
| 백준 2869 (Java) (1) | 2023.12.03 |