누적합(Prefix Sum) 알고리즘 완전 정복
배열에서 특정 구간의 합을 여러 번 빠르게 구해야 하는 상황, 코딩 테스트에서 정말 자주 나옵니다.이때 유용하게 사용되는 기법이 바로 Prefix Sum (누적합)입니다.📌 Prefix Sum이란?Prefix Sum은 배열의 각 위치까지의 누적합을 미리 계산해두고,이후에 특정 구간의 합을 O(1) 시간에 계산하는 알고리즘입니다.예: 배열 A = [3, 1, 4, 1, 5, 9]Prefix Sum 배열 S = [0, 3, 4, 8, 9, 14, 23]→ S[i]는 A[0]부터 A[i-1]까지의 합을 의미합니다.이렇게 해두면 구간 [i, j]의 합은 다음과 같이 계산할 수 있습니다:S[j+1] - S[i]💡 시간 복잡도 비교방식사전 처리구간 합 계산Brute ForceXO(N)Prefix SumO(N)O..
알고리즘/개념
2025. 6. 9. 15:33
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 그리디
- Prefix Sum
- BFS
- 파이썬
- 누적합
- 순열
- time()
- 코딩테스트
- 다이나믹프로그래밍
- 소수판별
- 중복제거
- 조합
- 복잡도
- 최적화
- 투포인터
- 시간복잡도
- TimeComplexity
- 탐색
- GREEDY
- numpy
- graph
- 그래프알고리즘
- 순코딩
- bfs_dfs
- 걸린시간
- dfs
- prefix
- 라이브러리없이
- 소수
- 에라토스테네스의체
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 |
글 보관함