누적합이란?누적합(Prefix Sum)은 배열이나 리스트에서 특정 구간의 합을 빠르게 계산하기 위해 사용하는 알고리즘 기법입니다.일반적으로 입력 배열의 첫 번째 원소부터 특정 위치까지의 합을 저장한 배열을 말하며, 사용됩니다.즉, 배열의 원소들을 더한 중간 결과를 미리 저장함으로써, 반복 계산을 최소화하고 효율성을 높입니다. 예시 그림을 살펴보면 이해가 쉬울 것입니다. 입력으로 [2,4,6,8,10] 이라는 배열이 주어진다면, 누적합은 위와 같이 구할 수 있습니다. 그렇다면 왜 누적합을 사용해야 할까요? 누적합을 사용하는 이유효율적인 구간 합 계산일반적으로 배열에서 특정 구간의 합을 구하려면, 해당 구간의 원소를 하나씩 더해야 합니다.이 경우 시간복잡도는 구간의 길이인 O(n)이 됩니다.하지만 누적합 ..
문제 https://www.acmicpc.net/problem/27210 27210번: 신을 모시는 사당 칠할 수 있는 돌상의 개수에 제한은 없으며, 반드시 연속한(인접한) 돌상들만 칠할 수 있음(띄엄띄엄 칠할 수 없음)에 유의하라. www.acmicpc.net 문제 풀이 같은 방향의 돌상의 길이가 가장 큰 구간을 구하는 전형적인 누적합 문제였습니다. 나는 두 개의 변수를 사용해서 각기 다른 돌상의 개수를 계산했습니다. 왼쪽 돌상의 개수를 left, 오른쪽 돌상의 개수를 right로 관리했습니다. 입력을 탐색하면서, 왼쪽 돌상이라면 left ++, right -- 오른쪽 돌상이라면 right++, left--를 해줬습니다. 추가적으로 우리는 연속적인 구간의 최대합을 원하기 때문에 left와 right가 ..
문제 https://www.acmicpc.net/problem/2208 2208번: 보석 줍기 화영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1 ≤ N ≤ 100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 화영이는 가급적 많은 이득 www.acmicpc.net 문제 풀이 문제가 길지만, 문제의 핵심은 M개의 보석을 연속적으로 주워야 한다는 사실이다. 핵심을 지키면서 주울 수 있는 보석의 최대값을 구하는 전형적인 누적합 문제이다. 나는 i번째의 보석을 이동할 때의 누적합을 accumulateSum 이라는 1차 배열로 잡았다. 따라서 accumulateSum[4]라면 4번째의 보석까지 이동했을 때의 누적합이다. 즉 여기는 1~4번째 보석의 ..
