문제 소개
이번 글에서는 고유한 정수로 이루어진 배열 arr을 첫 번째 인자로, 목표 합 target을 두 번째 인자로 받는 JavaScript 함수를 작성해 보겠습니다.
함수의 목표는 숫자의 중복 사용을 허용하면서 목표 합을 만들 수 있는 모든 조합의 개수를 세어 반환하는 것입니다.
예를 들어, 함수의 입력이 다음과 같다면 —
const arr = [1, 2, 3];
const target = 4;
출력 결과는 다음과 같아야 합니다 —
const output = 7;
출력 설명
목표 합 4를 만들 수 있는 가능한 조합은 총 7가지입니다 —
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
여기서 주목할 점은 (1, 2)와 (2, 1)처럼 순서가 다르면 서로 다른 조합으로 계산된다는 것입니다. 즉, 순열(permutation) 관점에서 경우의 수를 세는 문제입니다.
접근 방식: 메모이제이션을 활용한 재귀
단순 재귀로 해결하면 동일한 하위 문제를 반복해서 계산하게 되어 비효율적입니다. 따라서 이미 계산한 값을 객체(map)에 저장해 두고 재사용하는 메모이제이션(memoization) 기법을 적용하면 시간 복잡도를 크게 줄일 수 있습니다.
- 목표 값이 0이 되면 유효한 조합 하나를 찾은 것이므로 1을 반환합니다.
- 이미 계산된 목표 값이라면 저장된 결과를 그대로 반환합니다.
- 각 숫자에 대해 목표 값보다 작거나 같은 경우, 남은 목표 값으로 재귀 호출하여 경우의 수를 누적합니다.
예제 코드
위 접근 방식을 구현한 코드는 다음과 같습니다 —
const arr = [1, 2, 3];
const target = 4;
const sumUpto = (nums = [], target = 1, map = {}) => {
if (target === 0){
return 1;
};
if (typeof map[target] != "undefined"){
return map[target];
};
let res = 0;
for (let i = 0; i<nums.length; i++) {
if (target >= nums[i]){
res += sumUpto(nums, target - nums[i], map);
};
};
map[target] = res;
return res;
};
console.log(sumUpto(arr, target));
실행 결과
코드를 실행하면 콘솔에 다음과 같이 출력됩니다 —
7
마무리
이 알고리즘은 메모이제이션 덕분에 각 목표 값마다 한 번씩만 계산되므로, 시간 복잡도는 O(target × nums.length), 공간 복잡도는 O(target)입니다. 입력 배열이 커지거나 목표 합이 클 때도 효율적으로 동작하며, 동적 프로그래밍(DP)의 대표적인 응용 사례인 '동전 교환(Coin Change)' 문제와 동일한 유형입니다.