[알고리즘] 경우의 수(순열 / 조합) JS

알고리즘: 경우의 수 구하기

"경우의 수 구하기"는 주어진 문제에서 가능한 경우들을 계산하는 알고리즘을 의미합니다. 다양한 문제에서 "경우의 수"를 구할 때 자주 등장하는 알고리즘 방법론으로는 **순열(permutation)**과 **조합(combination)**이 있습니다. 이들을 계산하는 방법을 JavaScript 코드로 설명하고, 블로그 글에 적합하게 쉽게 설명할 수 있도록 정리해보겠습니다.

1. 경우의 수 구하기 기본 개념

경우의 수를 구하는 기본적인 아이디어는 순서가 중요한지 아닌지를 기준으로 두 가지로 나눠집니다.

• 순열(permutation): 순서가 중요한 경우, 예를 들어 카드에서 카드를 뽑는 순서가 중요할 때.
• 조합(combination): 순서가 중요하지 않은 경우, 예를 들어 친구들 중 3명을 선택할 때 순서는 중요하지 않음.

 

2. 순열 (Permutation)

순열은 주어진 수에서 순서를 고려하여 선택하는 경우의 수입니다. 예를 들어, ABC에서 2개의 문자를 고를 경우, AB, BA, AC, CA, BC, CB와 같이 6가지 경우가 나옵니다.

순열을 구하는 알고리즘 (JavaScript)

순열을 구할 때, 백트래킹(backtracking) 또는 재귀(recursion) 방법을 사용할 수 있습니다. 아래는 3개의 원소에서 순서대로 2개를 선택하는 순열을 구하는 JavaScript 코드입니다:

function permutation(arr, selected = [], result = []) {
    if (selected.length === 2) { // 2개 선택했을 때
        result.push([...selected]);
        return;
    }
    
    for (let i = 0; i < arr.length; i++) {
        selected.push(arr[i]); // 선택한 원소 넣기
        permutation(arr.slice(0, i).concat(arr.slice(i + 1)), selected, result); // 나머지 원소로 재귀 호출
        selected.pop(); // 원소 빼기
    }
    return result;
}

const arr = ['A', 'B', 'C'];
console.log(permutation(arr));

설명:

• arr.slice(0, i).concat(arr.slice(i + 1))는 현재 원소를 제외한 나머지 원소들을 대상으로 재귀 호출을 하여 순서를 고려해 순열을 만듭니다.
• selected.length === 2일 때, 2개의 원소가 선택되었으므로 결과 배열에 추가합니다.

[ [ 'A', 'B' ], [ 'A', 'C' ], [ 'B', 'A' ], [ 'B', 'C' ], [ 'C', 'A' ], [ 'C', 'B' ] ]

 

---

3. 조합 (Combination)

조합은 순서가 중요하지 않은 경우의 수입니다. 예를 들어, 5명 중 3명을 고를 때 순서는 상관없이 어떤 3명을 고를지가 중요합니다. 이때 가능한 모든 조합을 구하는 것입니다.

조합을 구하는 알고리즘 (JavaScript)

조합을 구할 때는 재귀나 백트래킹을 사용하여 가능한 모든 경우를 나열합니다.

function combination(arr, count, start = 0, selected = [], result = []) {
    if (selected.length === count) {
        result.push([...selected]); // count만큼 선택되었으면 결과에 추가
        return;
    }

    for (let i = start; i < arr.length; i++) {
        selected.push(arr[i]); // 원소 선택
        combination(arr, count, i + 1, selected, result); // 재귀적으로 나머지 원소들에 대해 탐색
        selected.pop(); // 원소를 빼고 돌아가며 다른 경우 탐색
    }

    return result;
}

const arr = ['A', 'B', 'C', 'D', 'E'];
console.log(combination(arr, 3));

설명:

• combination(arr, count) 함수는 주어진 배열 arr에서 count개의 원소를 고르는 조합을 구하는 함수입니다.
• start는 탐색을 시작할 인덱스를 의미하며, 선택된 원소는 selected에 저장되고, 선택된 조합이 count개가 되면 결과에 추가됩니다.

[ [ 'A', 'B', 'C' ], [ 'A', 'B', 'D' ], [ 'A', 'B', 'E' ], [ 'A', 'C', 'D' ], [ 'A', 'C', 'E' ], [ 'A', 'D', 'E' ], [ 'B', 'C', 'D' ], [ 'B', 'C', 'E' ], [ 'B', 'D', 'E' ], [ 'C', 'D', 'E' ] ]

 

4. JavaScript에서 조합과 순열의 차이점

• **순열 (Permutation)**은 순서가 중요한 경우로, 원소의 위치에 따라 다른 경우의 수를 생성합니다.
• **조합 (Combination)**은 순서가 중요하지 않은 경우로, 원소를 고르는 순서와 상관없이 조합을 구합니다.