글을 시작하며

알고리즘의 기초 중 하나인 순열, 조합, 부분집합 알고리즘에 대해 알아보려합니다. 이번 글에서는 각 개념에 대해 간략히 설명하고, JavaScript로 어떻게 구현할 수 있는지 살펴보고자 합니다.

순열 (Permutation)

순열은 집합에서 서로 다른 n개 원소 중 r개를 뽑아서 한 줄로 나열하는 것을 의미합니다. 예를 들어, (A, B, C)라는 집합에서 두 원소를 고른다면, 아래와 같이 6가지 경우의 수가 있습니다.

(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)

순열의 개수는 n! / (n-r)!으로 계산할 수 있습니다. 여기서 n은 집합의 원소 개수, r은 선택할 원소의 개수입니다.

// 순열
function getPermutations(arr, selectNum) {
  const results = [];

  if (selectNum === 1) return arr.map((el) => [el]);

  arr.forEach((fixed, index, origin) => {
    const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
    const permutations = getCombinations(rest, selectNum - 1);
    const attached = permutations.map((el) => [fixed, ...el]);

    results.push(...attached);
  });

  return results;
}

// 중복 순열
function getPermutationsWithRepetition(arr, selectNum) {
  const results = [];

  if (selectNum === 1) return arr.map((el) => [el]);

  arr.forEach((fixed) => {
    const permutations = getPermutationsWithRepetition(arr, selectNum - 1);
    const attached = permutations.map((el) => [fixed, ...el]);

    results.push(...attached);
  });

  return results;
}

조합 (Combination)

조합은 집합에서 순서를 고려하지 않고 원소를 선택하는 방법입니다. 예를 들어, (A, B, C)라는 집합에서 두 원소를 고른다면, 아래와 같이 3가지 경우의 수가 있습니다.

(A, B), (A, C), (B, C)

조합의 개수는 n! / r!(n-r)!로 계산됩니다.

순열과 조합의 차이점은 순열은 순서가 중요하고, 조합은 순서가 중요하지 않다는 점입니다. 순열에서는 (A, B)와 (B, A)를 다른 경우로 취급하지만, 조합에서는 같은 경우로 취급합니다.

// 조합
function getCombinations(arr, selectNum) {
  const results = [];

  if (selectNum === 1) return arr.map((el) => [el]);

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest, selectNum - 1);
    const attached = combinations.map((el) => [fixed, ...el]);

    results.push(...attached);
  });

  return results;
}

// 중복 조합
function getCombinationsWithRepetition(arr, selectNum) {
  const results = [];

  if (selectNum === 1) return arr.map((el) => [el]);

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index);
    const combinations = getCombinationsWithRepetition(rest, selectNum - 1);
    const attached = combinations.map((el) => [fixed, ...el]);

    results.push(...attached);
  });

  return results;
}

부분집합 (Subset)

부분집합은 주어진 집합에서 원소의 순서나 개수에 상관없이 가능한 모든 부분집합을 구하는 문제입니다. 예를 들어, (A, B, C)라는 집합의 부분집합은 아래와 같이 8가지 경우의 수가 있습니다.

(), (A), (B), (C), (A, B), (B, C), (A, C), (A, B, C)

부분집합의 개수는 2^n으로 계산됩니다.

function getSubsets(arr) {
  const subsets = [[]];

  arr.forEach((value) => {
    subsets.push(...subsets.map((subset) => [...subset, value]));
  });

  return subsets;
}

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

결론

순열, 조합, 부분집합은 알고리즘 문제를 해결하는 데 있어 매우 유용하게 사용되는 개념들입니다. 백준 N과 M 시리즈들은 순열, 조합, 부분집합을 연습하는데 좋은 문제들입니다. 이외에도 다양한 문제를 해결해보며 순,조,부에 익숙해져보세요!

순열, 조합, 부분집합 feat. Javascript

순열, 조합, 부분집합에 대한 개념과 JavaScript로 구현하는 방법에 대해 알아보자

글을 시작하며

순열 (Permutation)

조합 (Combination)

부분집합 (Subset)

결론