Prefix Sum(접두사 합)
부분합, 누적합, 구간합 등으로 불리며 해당 합을 빠르게 구하는 알고리즘이다.
사실 알고리즘 치고는 매우 간단하다.
이 알고리즘의 원리는 다음과 같다.
각각의 숫자까지의 합을 미리 계산하여 저장해놓고 그 저장한 값을 활용하여 구간합을 구한다.
사실 접두사합, 구간합, 부분합 알고리즘을 검색하면 많은 블로그가 나올 텐데,
기본적으로 접두사 합 알고리즘의 공식을 다음과 같이 설명하고 있다.
P[Right] - P[Left - 1]
크게 틀린 공식은 아니니 일단 이런 식으로 사용하는구나 정도는 알고 진행하면 좋다.
다른 알고리즘도 마찬가지겠지만 문제에 따라 정해진 공식을 사용할 수 없는 경우가 많다.
예를 들어 숫자 [100, 101, 102, 103, 104]가 주어졌다고 가정한다면, 여기서 0번째부터 ~ 2번째까지의 합을 구하시오라고 한다면 위 공식을 그대로 사용할 수 있을까?
답은 아니요다.
위 공식은 첫 번째 인덱스 값이 0이 아닌 1이기 때문이다.
배열로 문제를 풀다 보면 첫 번째 인덱스를 0으로 지칭하는지, 1로 지칭하는지에 따라 유연한 사고가 필요하다.
뭐 아무튼 저 공식을 그대로 외울게 아니라 이 알고리즘의 원리가 어떤 식인지만 알고 문제에 따라 해결 방식을 다르게 하면 되는 게 전부이다.
예제 1) 특정 구간의 합을 담은 배열을 반환하라. (첫 번째가 0인 경우)
// numbers: [10, 20, 30, 40, 50, 60] (구간 합 대상 숫자 배열)
// S: [1, 2] (시작지점)
// F: [2, 4] (종료지점)
function solution(numbers, S, F) {
let answer = [];
const sums = [0];
// 1. 구간합 미리 저장
for (let i = 0; i < numbers.length; i++) {
sums[i + 1] = sums[i] + numbers[i];
}
// 2. 구간합 구하기
for (let i = 0; i < S.length; i++) {
answer.push(sums[F[i] + 1] - sums[S[i]]);
}
return answer;
}
solution([10, 20, 30, 40, 50, 60], [1, 2], [2, 4]);
// [50, 120]이 문제는 본문에서 설명했던 것처럼 첫 번째 숫자의 위치를 0번째로 지칭할 경우 이런 식으로 문제를 풀 수 있다.
[10, 20, 30, 40, 50, 60]에서 1번째부터 2번째까지 의 합은 50이 나오고, 2번째부터 4번째까지의 합은 120이 나온다.
예제 2) 특정 구간의 합을 담은 배열을 반환하라. (첫 번째가 1인 경우)
// numbers: [10, 20, 30, 40, 50, 60] (구간 합 대상 숫자 배열)
// S: [1, 2] (시작지점)
// F: [2, 4] (종료지점)
function solution(numbers, S, F) {
let answer = [];
const sums = [0];
// 1. 구간합 미리 저장
for (let i = 0; i < numbers.length; i++) {
sums[i + 1] = sums[i] + numbers[i];
}
// 2. 구간합 구하기
for (let i = 0; i < S.length; i++) {
answer.push(sums[F[i]] - sums[S[i] - 1]);
}
return answer;
}
solution([10, 20, 30, 40, 50, 60], [1, 2], [2, 4]);
// [30, 90]이게 본문에서 사용한 공식을 그대로 이용한 경우이다.
구간합 구하기 부분만 조금 수정해서 사용하면 된다. 당연히 결과 값이 전혀 달라진다.
인덱스의 의미가 달라졌기 때문이다.
댓글