백준이나 프로그래머스를 통해 문제를 풀 때 , 알고리즘 분류에 누적 합이라는 키워드가 있는 것을 볼 수 있습니다. 누적 합이라는 것이 무엇일까요 ?
누적 합이란 수열 An에 대해서 각 인덱스까지의 구간의 합을 구하여 저장하는 것을 뜻합니다.
수학 시간에 배웠던 시그마의 결과가 저장된다고 생각하면 되는데요. 어떤 경우에서 누적 합을 이용한 풀이가 효과적일지 예시를 들어 알아보겠습니다.
예를 들어 , 특정 구간의 합을 구해야 한다고 가정해봅시다. 특정 구간의 합을 여러 개 구해야 한다고 했을 때 , x번째 부터 x+n번째 까지의 합을 M개 구해야 한다고 치면 O(NM)의 Time Complexity가 나오게 됩니다.
그러나 , 누적 합 배열을 만들어두게 되면 누적 합을 만들 때 소요한 O(n)을 제외한 모든 연산엔 O(1)의 Time Complexity가 나오게 됩니다.
An=2n-1 이라고 했을 때 n=6까지의 누적합 배열입니다. n=3부터 6까지의 누적 합을 알고 싶다라고 하면 , 6까지의 누적 합에서 2까지의 누적 합을 빼면 되겠죠 ?
또한 n=7까지의 누적 합을 알고 싶다면 6까지의 누적 합에 7만 더하면 될 것입니다.
이렇게 동일한 계산을 반복해야 할 때 ,이전에 계산한 값들을 저장해두는 방식을 메모이제이션(Memoization)이라고 합니다. 이러한 메모이제이션 기법은 dp에서도 핵심 개념으로 잡히니 잘 알아두고 있는 것이 좋을 것 같습니다.
백준 문제를 통해 누적 합 개념을 적용해보겠습니다.
문제를 읽어보면 결국엔 조교가 지시한 모든 명령들을 합한 배열에 기존 연병장 높이 배열을 더하면 된다는 것을 알 수 있습니다. 그렇다면 가장 첫 번째로 드는 생각은 임의의 배열을 만든 이후에 조교가 지시한 것들을 다 더하면 되는 거 아닌가 ? 라는 생각이 듭니다. 예제 입력으로 한 번 볼까요 ?
조교의 지시를 모두 저장하는 임의의 배열을 만들어보겠습니다.
need=[0,0,0,0,0,0,0,0,0,0]
첫 번째 지시를 수행했을 때 -> need=[-3,-3,-3,-3,-3,0,0,0,0,0]
두 번째 지시를 수행했을 때 -> need=[-3,-3,-3,-3,-3,5,5,5,5,5]
세 번째 지시를 수행했을 때 -> need=[-3,-1,-1,-1,-1,7,7,5,5,5]
이 배열을 [1,2,3,4,5,-1,-2,-3,-4,-5]와 더해주면 예제 출력처럼 나올 겁니다 .
하지만 , 제한 조건을 보면 N과 M은 최대 10만이기에 위와 같은 풀이로 진행하면 시간 초과 문제를 겪게 됩니다.
다른 풀이로는 어떻게 풀 수 있을까요 ?
어떤 배열을 누적합으로 만들면 need=[-3,-1,-1,-1,-1,7,7,5,5,5]과 같은 결과가 나올까 고민해보면 됩니다.
예시로 첫 번째 지시를 수행했을 때 need=[-3,0,0,0,0,3,0,0,0,0] 로 만들어보고 이를 누적합 배열로 만들어보면 prefixSum=[-3,-3,-3,-3,-3,0,0,0,0,0]이 될 것입니다.
이 원리를 이용해서 문제를 일반화해보면 조교의 모든 지시에 need[a-1]+=k , need[b]+=-k를 해주고 누적합 배열을 만들어준 후 , 연병장 배열에 더해주면 정답이 나오게 되는 것을 알 수 있습니다.
// 19951
function solution(input) {
const [n, m] = input[0];
let arr = input[1];
// 누적합 배열을 만들기 위한 준비를 해줍니다.
const need = Array(n + 1).fill(0);
for (let i = 2; i < m + 2; i++) {
const [a, b, k] = input[i];
need[a - 1] += k;
need[b] += -k;
}
// 누적합 배열을 만들어줍니다.
for (let i = 1; i < need.length; i++) {
need[i] += need[i - 1];
}
// 조교들의 지시를 기존 연병장 배열에 더해줍니다.
arr = arr.map((el, idx) => {
return el + need[idx];
});
console.log(arr.join(" "));
}
const rl = require("readline").createInterface({
input: process.stdin,
output: process.stdout,
});
const input = [];
rl.on("line", (line) => {
input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", () => {
solution(input);
process.exit();
});
