[알고리즘] 자바스크립트로 조합을 구현해보자! - 백트래킹

fgStudy·2022년 6월 12일
3
post-thumbnail

조합

조합은 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다. 예시로 [1,2,3] 배열에서 2개를 선택해 만든 조합은 아래와 같다.

[1,2]
[1,3]
[2,3]

조합 알고리즘

조합 알고리즘 설명은 해당 사이트를 참고하였다.

조합은 기호 nCr로 나타내며 nCr = n-1Cr-1 + n-1Cr이라는 성질을 가지고 있다. 즉 조합은 하나의 원소를 선택할 경우 + 하나의 원소를 선택하지 않을 경우 이 둘의 합을 나타낸다.

예를 들어 배열 (1,2,3) 중에서 2개를 뽑는 조합을 구한다고 생각해보자.

  • (1, X) - 1을 뽑는 경우(하나의 원소를 선택할 경우)
    • 2개 중 하나는 뽑혔으므로 남은 원소 2가지 중 하나를 선택하면 된다(2C1).
    • 총 2개의 경우 (1,2) (1,3) -> 2C1
  • (X, X) - 1을 뽑지 않은 경우(하나의 원소를 선택하지 않은 경우)
    • 1은 이미 뽑혔으므로 남은 원소 2가지 중 2개를 선택하면 된다(2C2).
    • 총 1개의 경우 (2,3) -> 2C2

이처럼 2가지로 나뉠 수 있다.
즉 (1,2,3)에서 2개를 뽑는 조합은 두 가지 경우를 합해 (1,2), (1,3), (2,3) 총 3가지가 된다.


백트래킹을 이용해 구현

1. 로직 설명

배열 [1,2,3] 중 2개의 원소를 뽑아 조합을 만들어보자.

먼저 조합을 저장할 빈 배열을 크기 2만큼 생성한다. 배열 위에 있는 별은 현재 상태에 위치하는지를 나타낸다.

조합의 맨 처음 원소를 배열의 첫 번째 원소인 1로 설정한다.

조합의 두 번째 원소로 들어갈 수 있는 원소는 2와 3이다. 먼저 2로 채워넣어보자.

현재 상태에서 조합이 완성되었으므로([1,2]) 이전 상태로 돌아간다.

조합의 두 번째 원소로 들어갈 수 있는 원소는 3이다. 따라서 3을 채워넣는다.

현재 상태에서 조합이 완성되었으므로([1,3]) 이전 상태로 돌아간다.

첫 번째 원소가 1인 조합은 더 이상 만들 수 없으므로 이전 상태로 돌아간다.

조합의 첫 번째 원소로 들어갈 수 있는 원소는 2이다. 따라서 2를 채워넣는다.

조합의 두 번째 원소로 들어갈 수 있는 원소는 3이다. 따라서 3을 채워넣는다.

현재 상태에서 조합이 완성되었으므로([2,3]) 이전 상태로 돌아간다.

현재 상태에서 두 번째 원소로 들어갈 수 있는 원소가 더 이상 없다. 따라서 이전 상태로 돌아간다.

현재 상태에서 첫 번째 원소로 3이 들어올 수 있다. 하지만 두 번째 원소로 들어갈 수 있는 원소가 더 이상 없으므로 백트래킹은 종료된다.

따라서 배열 [1,2,3]에 대해 2개의 원소를 뽑아 만들 수 있는 배열은 [1,2], [1,3], [2,3] 총 3가지이다.


2. 백트래킹 코드

  • 배열 [1,2,3] 중 2개의 원소를 뽑아 조합을 만들어보자.
    아래 코드에서 arr는 [1,2,3], k는 2이다.

  • 조합을 저장할 변수 comb의 각 원소의 값을 0으로 초기화해준다. 백트래킹을 진행하면서 각 idx의 값을 업데이트 시켜줄 것이다.

  • 초기화한 comb에 대해 백트래킹을 진행하자. start는 사용할 수 있는 idx 범위를 나타내준다. start를 기준으로 for loop를 돌리면서 각 원소 값을 업데이트 시킨 다음 백트래킹을 진행하자.

  • 만약 idx가 k와 같아진다면 조합을 완성한 것이다. 예컨대 조합 [1,2]를 만든 것이다. 따라서 해당 조합을 answer에 push하고 리턴해준다. 리턴을 하게 되면 이전 상태로 돌아가게 된다.

  • 백트래킹이 전부 종료되면 answer에 원소를 두개 뽑아 만든 조합 [1,2], [1,3], [2,3]이 들어가 있다.

var combine = function(arr, k) {
    const answer = [];
    const comb = [...Array(k)].fill(0);
    backTracking(answer, comb, arr, k, 0, 0);
    return answer;
};

function backTracking(answer, comb, arr, k, idx, start) {
    if (idx === k) {
        return answer.push([...comb]);
    }
    
    for (let i=start; i<arr.length; i++) {
        comb[idx] = arr[i];
        backTracking(answer, comb, arr, k, idx+1, i+1);
    }
}

// [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ]
console.log(combine([1,2,3], 2));

(ref) 조합 알고리즘 설명

profile
지식은 누가 origin인지 중요하지 않다.

0개의 댓글