2021_04_20

TIL - Algorithm with Math

1. Algorithm with Math

이번시간에는 알고리즘을 구현할 때 사용할 수 있는 수학적 개념들에 대하여 공부하였다.

1) GCD/LCM
GCD(최대공약수)는 둘 이상의 공약수 중에서 최대인 수를 말한다.
GCD를 구하는 알고리즘은 다음과 같다.

let getGCD = (A, B) => { //두 개의 수를 입력받는다.
    if(A % B === 0) {
      return B;
    }
    return getGCD(B, A % B);
}

LCM(최소공배수)는 둘 이상의 공배수 중에서 최소인 수를 말한다.
LCM을 구하는 알고리즘은 다음과 같다.

let getLCM = (A, B) => { //두 개의 수를 입력받는다.
  return a*b / getGCD(A, B)
}

2) 순열/조합
순열은 순서를 생각하며 경우의 수를 따지는 것이다.
순열을 이용하여 숫자를 나열하는 알고리즘은 다음과 같다.

function permutator(inputArr) {
  let results = [];
  function permute(arr, memo) {
    let cur; 
    for (var i = 0; i < arr.length; i++) {
      cur = arr.splice(i, 1);
      if (arr.length === 0) {
        results.push(memo.concat(cur));
      }
      permute(arr.slice(), memo.concat(cur));
      arr.splice(i, 0, cur[0]);
    }
    return results;
  }
  return permute(inputArr, []); 
}

재귀함수를 이용해서 구현하였다.