1. 서론
취업을 준비하면서 많은 개발자들이 알고리즘 문제를 풀기 위한 코딩테스트를 준비합니다. 특히 자바스크립트를 사용하는 경우, 조합(combination) 문제는 자주 등장하는 주제 중 하나입니다. 조합은 주어진 집합에서 특정 개수의 원소를 선택할 때 어떤 방식으로 선택할 수 있는지를 다룹니다. 이 글에서는 조합의 개념을 명확히 하고, 이를 활용한 알고리즘 문제를 제시하여 해결 과정을 상세히 설명하겠습니다.
2. 조합의 개념
조합은 순서에 상관없이 특정 개수의 원소를 선택하는 방법을 의미합니다. 예를 들어, {A, B, C}라는 집합에서 2개를 선택하는 조합은 {A, B}, {A, C}, {B, C} 이렇게 총 3가지입니다. 조합은 다음과 같은 수학적 공식을 통해 계산할 수 있습니다.
- nCk = n! / (k! * (n-k)!)
여기서 n은 집합의 크기, k는 선택할 원소의 개수, !는 팩토리얼을 의미합니다.
3. 알고리즘 문제
문제: 조합의 합
주어진 정수 배열 arr와 정수 target가 있습니다. 배열에서 원소를 조합하여 target과 같은 합을 만들 수 있는 모든 조합을 구하시오. 각 조합은 원소의 순서를 다르게 하더라도 동일한 조합으로 취급합니다.
입력 예시
- arr = [2, 3, 6, 7]
- target = 7
출력 예시
- 결과: [[7], [2, 2, 3]]
4. 문제 해결 과정
이 문제를 해결하기 위해 재귀함수와 백트래킹(Backtracking) 기법을 사용할 수 있습니다. 함수를 설계할 때 고려해야 할 사항은 다음과 같습니다.
- 현재 선택한 원소의 합이
target과 같으면 해당 조합을 저장합니다. - 현재 선택한 원소의 합이
target을 초과하면 함수를 종료합니다. - 각 원소를 반복적으로 선택하면서 조합을 만듭니다.
4.1. 자바스크립트 코드
function combinationSum(arr, target) {
const results = [];
function backtrack(start, path, sum) {
if (sum === target) {
results.push([...path]);
return;
}
if (sum > target) {
return;
}
for (let i = start; i < arr.length; i++) {
path.push(arr[i]);
backtrack(i, path, sum + arr[i]);
path.pop();
}
}
backtrack(0, [], 0);
return results;
}
const arr = [2, 3, 6, 7];
const target = 7;
console.log(combinationSum(arr, target));
4.2. 코드 분석
위 코드는 다음과 같은 단계를 통해 문제를 해결합니다.
- 함수 정의:
combinationSum함수를 정의하고, 내부에backtrack함수를 선언하여 조합을 생성합니다. - 재귀 호출: 각 원소를 선택한 후, 그 원소를 포함한 조합을 계속해서 재귀적으로 탐색합니다. 이때
start라는 변수를 사용하여 이미 선택한 원소를 다시 선택하지 않도록 합니다. - 합 비교: 현재까지의 합
sum이target과 동일할 경우, 현재의 조합path를 결과 배열에 추가합니다. - 백트래킹: 재귀 호출 후, 선택한 원소를 제거하고 다음 원소로 이동합니다.
5. 시간 복잡도
이 문제의 시간 복잡도는 최악의 경우 O(2^n)입니다. 각 원소를 포함할지 말지를 결정하는데, 이로 인해 모든 가능한 조합을 탐색하기 때문입니다. 비록 최악의 경우가 존재하더라도, 조합의 개수가 다소 적을 경우 이러한 방법으로도 문제를 해결할 수 있습니다.
6. 결론
오늘은 자바스크립트를 사용하여 조합 문제를 해결하는 방법에 대해 알아보았습니다. 조합의 개념을 이해하고, 백트래킹을 통한 재귀적 접근 방식을 통해 문제를 효과적으로 해결할 수 있음을 보여주었습니다. 코딩테스트에서 조합 문제는 빈번히 등장하기 때문에, 이러한 문제들에 대한 이해와 연습이 필요합니다. 다양한 문제를 풀어보며 실력을 키우시길 바랍니다.
7. 참고 자료
- LeetCode – 알고리즘 문제 풀이 플랫폼
- GeeksforGeeks – 다양한 자료구조와 알고리즘 강의