JavaScript로 인접하지 않은 요소의 최대 합 부분집합 구하기

문제 소개

정수로 이루어진 배열을 입력받아, 서로 인접하지 않은(non-adjacent) 요소들로 구성된 부분집합 중에서 합이 가장 큰 것을 찾는 JavaScript 함수를 작성해야 합니다.

마지막으로, 함수는 찾아낸 부분집합의 합을 계산하여 반환해야 합니다.

예시

입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [3, 5, 7, 8, 10];

이때 기대하는 출력값은 20입니다. 인접하지 않은 요소들만으로 만들 수 있는 최대 합 부분집합은 3, 7, 10이며, 그 합이 3 + 7 + 10 = 20이기 때문입니다.

구현 코드

이 문제를 해결하는 코드는 다음과 같습니다.

const arr = [3, 5, 7, 8, 10];
const maxSubsetSum = (arr = []) => {
    let min = -Infinity;
    const helper = (arr, ind) => {
        if (ind < 0) {
            return min;
        }
        let inc = helper(arr, ind - 2);
        let notInc = helper(arr, ind - 1);
        inc = inc === min ? arr[ind] : Math.max(arr[ind], arr[ind] + inc);
        return Math.max(inc, notInc);
    };
    return helper(arr, arr.length - 1);
};
console.log(maxSubsetSum(arr));

출력 결과

위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.

20

알고리즘 동작 원리

이 코드는 재귀 호출을 활용한 동적 계획법(Dynamic Programming) 스타일의 접근 방식을 사용합니다. 각 인덱스에서 고려해야 할 선택지는 두 가지입니다.

• 현재 요소를 포함하는 경우: 인접한 요소는 사용할 수 없으므로, 두 칸 앞인 ind - 2 위치로 이동하여 탐색을 계속합니다.
• 현재 요소를 포함하지 않는 경우: 바로 앞인 ind - 1 위치로 이동하여 나머지 요소들을 대상으로 탐색을 계속합니다.

두 경우 중 더 큰 값을 반환하면서 재귀적으로 최대 합을 구하게 되며, 인덱스가 0보다 작아지면 -Infinity를 반환해 탐색을 종료합니다.

참고로 위 구현은 메모이제이션(memoization) 없이 순수 재귀로 작성되었기 때문에 시간 복잡도가 지수(exponential) 수준입니다. 배열의 길이가 클 가능성이 있다면 계산 결과를 객체나 Map에 캐싱하여 O(n) 수준으로 성능을 개선할 수 있습니다.