조합 알고리즘

이 글에서는 조합을 재귀를 통해서 구현하는 방법에 대해서 알아보자.

브루트포스 알고리즘에서 가장 많이 사용되는 방법이 순열과 조합 등으로 모든 경우의 수를 모두 계산해본 뒤에 원하는 결과 값을 찾는 방식이다.

조합은 순서가 상관이 없는 모임을 의미한다.

순서가 상관 없기 때문에 { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3 } 모두 같은것으로 취급을 한다.

순서가 상관없기 때문에 1, 2, 3 이라는 3개의 숫자로 이루어져있다는 점에서 똑같은 취급을 하는 것이 조합이다.

핵심은 조합을 구현할 때, 하나의 시작점을 정한다면, 그 시작점 이전에 나온 원소들을 다시 쳐다보지 않는다.

이를 기억하며 아래의 구현 코드를 확인하자.

구현 코드

const combination = () => {
  const arr = [1, 2, 3, 4, 5]; // 조합에 사용되는 배열
  const selected = new Array(5).fill(false); // 이 배열을 통해 중복을 허용하지 않도록 해야한다.

  dfs(0, 0, arr, selected);
};

const dfs = (idx, cnt, arr, selected) => {
  // idx는 시작점을 결정해주는 변수이다. Idx를 시작점으로 삼는 순간, idx이전에 나온 원소는 무시
  // cnt는 현재 뽑은 원소의 갯수를 결정해주는 변수이다. 현재 뽑은 원소의 갯수가 우리가 최종적으로 뽑고자 하는 원소의 갯수와 일치한다면, 그 다음 프로세스를 진행하면 된다.

  if (cnt === 3) {
    const result = [];

    for (let i = 0; i < 5; i++) {
      if (selected[i] === true) {
        result.push(arr[i]);
      }
    }

    console.log(result.join(" "));

    return;
  }

  for (let i = idx; i < 5; i++) {
    if (selected[i] === true) continue;

    selected[i] = true;
    dfs(i, cnt + 1, arr, selected);
    selected[i] = false;
  }
};

combination();