백준 17425번 약수의 합을 푸는데 도저히 감이 안잡혀서 이 문제가 무슨 알고리즘으로 분류되었는지 봤더니 누적 합이라는게 있었다.
다른 것들은 어디서 한번 보거나 풀어본 것들이였는데 누적 합은 처음 보는지라 일단 누적 합 문제부터 풀어야겠다고 생각했다!
11659번: 구간 합 구하기4 문제
처음에는 예제에 나와있는 i번째 수부터 j번째 수까지 전부 더해주는 방식으로 풀었는데, 이렇게 푸니까 시간초과가 나왔다.
수의 개수 N과 합을 구해야 하는 횟수 M이 최대 100,000까지니까 최악의 경우 100,000 * 100,000번의 계산을 해야 하는 것이였다..
이러한 경우 누적 합 알고리즘을 이용해서 풀어야 한다!
누적 합이란?
누적 합은 말그대로 연속된 숫자의 누적된 합을 말한다. 예를 들어 [1, 2, 3, 4, 5]라는 배열이 있을 때 이 배열의 누적 합의 배열은 [1, 3, 6, 10, 15]이 된다.
누적 합의 장점
N개의 원소로 이루어진 배열이 주어졌을 때 M번의 부분 배열의 합을 구하는 경우에 누적 합을 사용하지 않으면 O(NM)의 시간이 걸리게 된다.
하지만 누적 합을 사용하게 되면 O(N+M)의 시간만 걸리기 때문에 시간을 많이 단축할 수 있다.
누적 합 구현
function cumulativeSum(arr) {
let cumsum = new Array(arr.length + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
cumsum[i + 1] = cumsum[i] + arr[i];
}
return cumsum;
}누적 합 배열은 위와 같이 구할 수 있다.
만약 [1, 2, 3, 4, 5] 배열에서 2번째 수에서 4번째 수까지의 합을 구하는 경우, 누적 합 배열은 [1, 3, 6, 10, 15]가 되고 여기서 4번째 원소에서 1번째 원소를 빼면 원하는 구간 값이 나온다.
즉, i번째에서 j번째 까지의 합은 cumsum[j] - cumsum[i-1]로 구할 수 있다!
11659번: 구간 합 구하기4 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const numbers = input[1].split(" ").map(Number);
const answer = [];
let cumsum = new Array(numbers.length + 1).fill(0);
for (let i = 0; i < numbers.length; i++) {
cumsum[i + 1] = cumsum[i] + arr[i];
}
for (let index = 2; index < input.length; index++) {
let [i, j] = input[index].split(" ").map(Number);
answer.push(cumsum[j] - cumsum[i - 1]);
}
console.log(answer.join("\n"));