순열, 조합, 중복순열, 수열, 최대공약수 코드모음

 

코딩테스트에서 주로 사용되는 순열, 조합 등을 함수화 시킨 코드입니다

필요한 부분에 삽입해서 사용하시면 됩니다

 

순열 코드

순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다 ( 순서 상관 o )

일반식 : nPr = n! / (n - r)!

5장에서 3장을 선택하는 모든 순열의 수 = P = (5 X 4 X 3 X 2 X 1) / (2 X 1) = 60

function permutation(arr, selectNum) {
  let result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixer = v;
    const restArr = arr.filter((_, index) => index !== idx);
    const permuationArr = permutation(restArr, selectNum - 1);
    const combineFixer = permuationArr.map((v) => [fixer, ...v]);
    result.push(...combineFixer);
  });
  return result;
}

조합 코드

조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다 ( 순서 상관x )

일반식: nCr = n! / (r! * (n - r)!)

5장에서 3장을 무작위로 선택하는 조합에서 모든 경우의 수 = 5C3 = 5! / (3! * 2!) = 10

function combination(arr, selectNum) {
  const result = [];
  if (selectNum === 1) return arr.map((v) => [v]);
  arr.forEach((v, idx, arr) => {
    const fixed = v;
    const restArr = arr.slice(idx + 1);
    const combinationArr = combination(restArr, selectNum - 1);
    const combineFix = combinationArr.map((v) => [fixed, ...v]);
    result.push(...combineFix);
  });
  return result;
}

중복 순열 코드

function rockPaperScissors (rounds) {
  // TODO: 여기에 코드를 작성합니다.
  if(rounds === undefined) rounds = 3;
  let arr = ["rock","paper","scissors"];
  let outArr =[];
  Permutation([],rounds,arr,outArr)
  return outArr
};

function Permutation(array, n, eachElements, outArr) {
  // TODO: 여기에 코드를 작성합니다.

  if (array.length == n) {
    outArr.push(JSON.parse(JSON.stringify(array)));
    return;
  }
  for (let el of eachElements) {
    array.push(el)
    Permutation(array, n, eachElements, outArr)
    array.pop()
  }
};

수열 코드

function permutation(arr, selectNum) {
  let result = [];
  // 개수가 한개라면 인자하나씩 배열로 감싸줌
  if (selectNum === 1) return arr.map((el) => [el]);

  // arr 전체 순환
  arr.forEach((v, idx, arr) => {
    // 인자
    const fixer = v;
    // arr의 index와 idx와 같은 않은것들만 restArr 배열에 담음
    const restArr = arr.filter((_, index) => index !== idx);
    // permutation함수에 arr를 restArr로 selectNum을 -1해서 재귀
    const permuationArr = permutation(restArr, selectNum - 1);
    // 인자를 담아놓은 fixer과 배열 v를 스프레드로 풀어서 하나의 배열로 만들고 매핑
    const combineFixer = permuationArr.map((v) => [fixer, ...v]);
    // result에 담아주면 끝
    result.push(...combineFixer);
  });
  return result;
}

최대공약수

const gcd = (a, b) => (a % b === 0 ? b : gcd(b, a % b));

참조

[수학] 순열, 조합 공식 총정리

30.md