TIL 46일차

시작하며

오늘은 수학에서 사용하는 개념들을 알고리즘에 적용시켜 실제 코드로 작성하는 법을 학습하였다. 순열, 조합 등 이미 알고 있었기 때문에 개념을 이해하는 것은 어렵지 않았으나 실제 코드로 작성하려니 막막함을 느꼈다. 여러 예시들을 찾아보면서 재귀를 사용해서 답을 구하는 과정을 이해하고 실제 코드로 작성할 수 있었다.

Algorithm

순열

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;
}

순열, 조합, 중복순열 모두 흡사한 형태로 코드를 작성할 수 있는데 다른 부분은 restArr를 어떻게 할당하냐에 따라 도출되는 값이 달라진다. 순열의 경우 이미 fixer로 선택한 값은 다시 선택되면 안되므로 해당 요소만 필터링해서 재귀가 이루어진다.

---

중복순열

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

중복순열은 fixer로 선택한 값이 다시 들어갈 수 있기 때문에 필터링하지 않고 모든 배열의 요소들이 재귀로 넘어가게 된다.

---

조합

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;
}

조합은 한번이라도 이전에 같은 조합이 만들어졌다면 순서 상관없이 중복되면 안되기 때문에 fixer로 선택한 값 이후의 인덱스를 가진 요소들만 재귀로 넘어가게 된다.

---

GCD(최대공약수)

function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

---

LCM(최소공배수)

function lcm(n, m) {
  function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
  }
  return (n*m) / gcd(n,m)
}

---

멱집합

function powerSet(elements) {
  let answer = [];
  function dfs(start=0, arr=[]) {
    answer.push(arr)
    for(let i =start; i < elements.length; i++) {
      dfs(i+1,[...arr, elements[i]])
    }
  }
  dfs();
  return answer
}

마치며

수학에서 사용하는 개념을 이해했다면 실제 코드를 보면서 어떤 방식으로 결과가 도출되는지를 바로 살펴보는 것이 챕터를 이해하는데 큰 도움이 되었다. 개념만 이해해서 실제로 효율적인 코드를 작성하는 것은 굉장히 어렵고 시간이 오래 걸리기 때문에 알고리즘을 보고 이해해서 내것으로 만드는 과정을 통해서 코스를 수월하게 진행할 수 있었다.