자바스크립트 코딩테스트 강좌, 조합 알아보기

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 – 다양한 자료구조와 알고리즘 강의