| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
Tags
- Noam Nisan
- C#
- 잡생각 정리글
- 박기현
- 이득우의 게임수학
- 게임 수학
- 전공자를 위한 C언어 프로그래밍
- 데이터 통신과 컴퓨터 네트워크
- booksr.co.kr
- 백준
- The Elements of Computing Systems 2/E
- unity6
- 생능출판
- 입출력과 사칙연산
- 주우석
- BOJ
- C
- JavaScript
- 김진홍 옮김
- 알고리즘
- hanbit.co.kr
- C++
- 밑바닥부터 만드는 컴퓨팅 시스템 2판
- 이득우
- https://insightbook.co.kr/
- 일기
- 메타버스
- HANBIT Academy
- Shimon Schocken
- (주)책만
Archives
- Today
- Total
목록Difference Array (1)
cyphen156
이번 글에서는 누적합과 계차라는 서로 반대 개념을 다룬다.이 둘을 다루기 전에 먼저 구간합에 대해 알아야 한다.구간합이란?수열이 있을 때 특정 구간(Chunk , Segment)단위로 요소들의 합을 빠르게 구하는 것이다.예: A=[2,4,5,1,3]A = [2, 4, 5, 1, 3]A=[2,4,5,1,3] 일 때, 구간합(2~4번 원소) = A[2]+A[3]+A[4]=4+5+1=10A[2] + A[3] + A[4] = 4 + 5 + 1 = 10A[2]+A[3]+A[4]=4+5+1=10.단순하게 구하면 O(N), 질의가 많아지면 비효율적.→ 이를 빠르게 하기 위해 누적합을 사용한다. 누적합(Prefix Sum) S[i]=A[1]+A[2]+⋯+A[i] 누적합은 수열의 요소들을 처음부터 자기 자신까지를 미리 ..
컴퓨터공학/알고리듬
2025. 9. 12. 18:24