<구간합>
º 합 배열을 이용하여 시간복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
예시1) 배열 인덱스 4부터 10까지의 합 (S[4] = A[0]~A[4] )
<합 배열 S를 만드는 공식>
º S[i] = S[i-1] + A[i]
( S[i-1] = S[0] + S[1]+ ... + S[i-1] )
예시)
< i부터 j까지의 구간 합을 구하는 공식 >
º S[j] - s[i-1]
예시)
Q.왜 S[j] - S[i-1] 공식을 사용하는걸까?
A.
1. A배열의 인덱스 2부터 5까지의 합을 구하려고 한다. 공식대로 하면 S[5] - S[1]을 해준다. 왜?
2. S[5]는 A[0]부터 A[5]까지의 합이 담겨있다.
3. S[1]은 A[0[부터 A[1]까지의 합이 담겨있다.
4. S[5]에서 S[1]을 뺴주게 되면 보라색으로 동그라미 쳐진 범위의 값이 나오게 된다.
5. 그 값이 처음 구하려 했던 2부터 5까지의 합이다.
(질문 : 배열의 데이터가 자주 바뀌면 어떡하지? ->(추후에 나올) 인덱스 트리(세그먼트 트리) 사용)
'inflearn > Do it! 알고리즘 코딩테스트 with C++' 카테고리의 다른 글
| 섹션2. 정렬(Sorting). 버블정렬(Bubble Sort) (1) | 2023.10.01 |
|---|---|
| 섹션1. 자료구조(Data Structure). 스택과 큐 (1) | 2023.10.01 |
| 섹션1. 자료구조(Data Structure). [투 포인터 실전 문제] 좋은 수 구하기(백준 1253) (1) | 2023.09.30 |
| 섹션1. 자료구조(Data Structure). 배열과 리스트 그리고 *벡터 (0) | 2023.09.28 |
| 섹션0. 코딩테스트 준비하기 (0) | 2023.09.28 |
