동적 프로그래밍으로 JavaScript 배열의 부분 합계 구하기

문제 소개

다음과 같은 숫자 배열이 있다고 가정해 보겠습니다.

const arr = [1, 2, 3, 4, 5];

앞쪽에서 요소를 하나씩 제거해 가면, 이 배열은 아래와 같이 단계별로 분리할 수 있습니다.

[1, 2, 3, 4, 5]
[2, 3, 4, 5]
[3, 4, 5]
[4, 5]
[5]
[]

우리가 작성해야 할 것은 이런 배열을 입력으로 받는 자바스크립트 함수입니다. 이 함수는 위에서 설명한 방식 그대로 배열을 분리한 뒤, 각 단계별 부분 배열의 합계를 담은 새로운 배열을 만들어 반환해야 합니다.

따라서 앞서 예시로 든 배열에 대한 출력 결과는 다음과 같습니다.

const output = [15, 14, 12, 9, 5, 0];

동적 프로그래밍 접근 방식

이 문제는 동적 프로그래밍(Dynamic Programming) 기법을 활용하면 매우 효율적으로 해결할 수 있습니다.

먼저 전체 배열의 합을 O(n) 시간 안에 한 번 계산합니다. 이 값이 곧 결과 배열의 첫 번째 요소가 됩니다. 그다음 반복문을 순회하면서 각 인덱스에 해당하는 요소 값을 합계에서 차감해 나가면, 결과 배열의 나머지 값들이 자연스럽게 완성됩니다.

예를 들어 15(전체 합)에서 1을 빼면 14, 여기서 다시 2를 빼면 12가 되는 식입니다. 이처럼 매번 부분 배열을 새로 순회하지 않고 이전 계산 결과를 재활용하기 때문에, O(n) 시간 복잡도와 상수 수준의 추가 공간만으로 문제를 해결할 수 있습니다.

구현 예제

const arr = [1, 2, 3, 4, 5];
const sumArray = (arr = []) => arr.reduce((a, b) => a + b, 0);
const partialSum = (arr = []) => {
    let sum = sumArray(arr);
    const res = [sum];
    for(let i = 0; i < arr.length; i++){
        const el = arr[i];
        sum -= el;
        res.push(sum);
    };
    return res;
};
console.log(partialSum(arr));

코드의 동작 흐름을 정리하면 다음과 같습니다.

1. sumArray: reduce 메서드를 사용해 배열의 전체 합을 구합니다.
2. partialSum: 전체 합을 초기값으로 결과 배열에 넣고, 반복문을 돌며 각 요소를 합에서 빼가며 새 값을 추가합니다.
3. 마지막에는 빈 배열([])의 합인 0까지 포함되어 결과가 완성됩니다.

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

[ 15, 14, 12, 9, 5, 0 ]