·자료구조
누적 합(Prefix Sum) 알고리즘은 배열의 부분 합을 빠르게 계산하기 위한 유용한 도구입니다. 이는 특히 여러 번의 부분 합 계산이 필요한 상황에서 매우 효율적입니다. 이 글에서는 누적 합의 개념, 기본적인 구현 방법, 그리고 이를 활용한 문제 해결 방법에 대해 자세히 설명하겠습니다. 누적 합(Prefix Sum)란❓누적 합은 주어진 배열의 각 원소까지의 합을 저장한 배열입니다. 수열 An에 대해서 구간[1, 1]의 합, 구간[1, 2]의 합, 구간[1, 3]의 합,..., [1, n]의 합을 누적 합이라고 합니다. 예를 들어, 배열 arr가 주어졌을 때, prefixSum[i]는 arr [0]부터 arr [i-1]까지의 합을 의미합니다. 예를 들어, i = 3일 때 prefixSum[3] ➡..
