누적합2 누적합 응용(feat. 2차원 배열) 2차원 배열에 대한 구간합 문제가 나왔는데 내용이 기록하기 좋은 것 같아서 작성해보려고 한다.누적합에 대한 내용보다는 문제를 살펴보면서 어떻게 누적합을 사용해서 풀었는지에 대해서 얘기하려고 한다.누적합(Prefix Sum)에 관한 내용은 아래를 참고해 주세요.누적합(Prefix Sum)백준 11660번 구간 합 구하기 5문제 내용을 간단히 얘기하자면 $ N \cdot N $ 크기의 표가 주어지고 $ (x1, y2) $부터 $ (x2, y2) $까지 합을 구하는 것이다.ex) $ N = 4 $이고, 표가 아래와 같이 채워져 있는 경우. (2, 2)부터 (3, 4)까지 합을 구하면 $ 3+4+5+4+5+6 = 27 $이다.1234234534564567 이때 누적합을 어떻게 사용하는지 알아보려고 한다.먼저 .. 2025. 2. 23. 누적합(Prefix Sum) 누적합(Prefix Sum)누적합은 요소들의 누적된 합의 의미를 얘기합니다.배열의 첫 번째 0번째 배열의 요소부터 누적시키면서 더한 배열을 활용합니다. 일부 구간에 대한 합을 구하는 문제에서 사용이 됩니다. 단, 배열의 값들이 변하지 않는다는 전제가 필요합니다. $ N = 5 $ 인 N 크기의 정수 배열 arr이 있을 때 여러 개의 구간 [a, b]에 대해 합을 구하려고 합니다. $ 1\leq a\leq b\leq N $$$ arr[a]+arr[a+1]+\cdots+arr[b] $$Index i01234arr[i]16425 간단하게 생각할 수 있는 방법은 반복문을 돌려서 각 요소를 더하는 것입니다. 이 방법은 각 쿼리에 대해 최대 $ O(N) $ 시간 복잡도를 가지고, 만약 M개의 쿼리가 주어지면 시간 .. 2025. 1. 19. 이전 1 다음
