728x90
구간 합 개념
: 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 (가능한 케이스 개수가 극단적으로 많을 경우 특히!)
*핵심: 합 배열 S의 정의
S[i] = A[0] + A[1] + A[2] + .... A[i-1] + A[i]
=> 기존 배열의 일정 범위의 합을 구하는 시간 복잡도: O(N)
=> A[i]~A[j]까지 배열 합: 최악은 i가 0이고 j가 N이므로.
<=> 합 배열을 미리 구해 놓으면 : O(1)로 감소
구현 공식: S[i] = S[i-1](재귀느낌) + A[i](특정 원소)
=> 이것을 기본으로, 문제에 따라 다양한 변용!
구간 합 구현
구현 공식: S[j] - S[i-1]
=> 이것을 기본으로, 문제에 따라 다양한 변용!
728x90
'개발 > CS study' 카테고리의 다른 글
| [알고리즘] 정렬 / Sorting / 삽입 정렬(Insertion Sorting) (0) | 2023.06.24 |
|---|---|
| [백준] 구간 합 / 구간 합 구하기 5 (0) | 2023.06.24 |
| [백준] 스택, 오큰수 구하기 (0) | 2023.06.23 |
| [알고리즘] 스택, 큐 (0) | 2023.06.23 |
| [프로그래머스] BFS, 단어 변환 (0) | 2023.05.14 |