문제

최대 공약수와 최소 공배수를 배워보자

최대 공약수, 최소 공배수

• 최대 공약수 : 두 수에 관해 공통된 약수 중 가장 큰 정수
  • 6의 약수 ➡️ 1, 2, 3, 6
    12의 약수 ➡️ 1, 2, 3, 4, 6, 12
• 최소 공배수 : 두 수에 관해 공통된 배수 중 가장 큰 정수
  • 6의 배수 ➡️ 6, 12, 24, 30, 36 ...
    12의 배수 ➡️ 12, 24, 36, 48 ...

나의 풀이

function solution(n, m) {
    // 최대 공약수
    let gcd = 1;
    for (let i = 2; i <= Math.min(n, m); i++) {
      if (n % i === 0 && m % i === 0) {
        gcd = i;
      }
    }
    // 최소 공배수
    let lcm = 1;
    while (true) {
      if (lcm % n === 0 && lcm % m === 0) {
        break;
      }
      lcm++;
    }
    return [gcd, lcm]
}

• 최대 공약수는 두 수의 공통약수가 해당되면 값을 할당하고, 그 다음 큰 게 또 있다면 덮어씌워서 결국 가장 큰 걸 찾으려고 코드를 짰음
• 최소 공배수는 while에 true를 줘 무한 반복하는 형식이지만 공통된 배수 중 '최소'를 찾으면 바로 반복을 끝내버리는 코드를 짰음, 반복의 변수 자체를 lcm으로 둬 카운트와 해당된 배수 자체가 중복되는 식으로 짰음

문제점

최소 공배수는 최대 공약수가 있으면 구하기 쉬웠음, 두 수를 곱하고 최대 공약수를 나누면 최소 공배수가 나옴,, 이걸 몰라 최소 공배수를 구하는데 컴파일 시간이 더 걸려버림,, 난 바보임, 이 것만 해줘도 컴파일 시간이 0.XXms로 내려간다.

유클리드 호제법

최대 공약수를 재귀 형식으로 구하는 방법론이다.

어떤 자연수 a, b가 있을 때 (a > b), 두 수의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다.

초기 코드의 문제점까지 해결하며 코드를 짜보자

function solution(n, m) {
  let g = gcd(n, m);
  return [g, (n * m) / g];
}
// 호제법으로 조건이 만족할 때까지 계속 나누는 것
let gcd = (a, b) => (a % b === 0 ? b : gcd(b, a % b));