TIL 12주차 GCD/LCM(최대공약수, 최소공배수), 순열/조합, 멱집합

순열 / 조합

순열 / 조합 정리

---

GCD / LCM

유클리드 호제법이란?

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고,
다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

최대 공약수

function gcd(m, n) {
  if (m % n === 0) return n;
  return gcd(n, m % n);
}

최소 공배수

최대공약수를 구했다면 최소공배수를 구하는 것은 쉽다.

function lcm(m, n) {
  return (m * n) / gcd(m, n);
}

---

멱집합

집합 {1, 2, 3}의 모든 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} 으로 나열할 수 있고, 이 부분집합의 총 개수는 8개이다. 그리고 이 모든 부분집합을 통틀어 멱집합이라고 한다.

즉, 어떤 집합이 있을 때, 이 집합의 모든 부분집합을 멱집합 이라고 한다

---

정규표현식

정규표현식 정리