Notice
Recent Posts
Recent Comments
Link
«   2026/02   »
일 월 화 수 목 금 토
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 more
Archives
Today
Total
관리 메뉴

목록Difference Array (1)

cyphen156

알고리듬 #8 누적합과 계차 : 효과적으로 수열 다루기

이번 글에서는 누적합과 계차라는 서로 반대 개념을 다룬다.이 둘을 다루기 전에 먼저 구간합에 대해 알아야 한다.구간합이란?수열이 있을 때 특정 구간(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
이전 Prev 1 Next 다음