최대공약수와 최대공배수

풀이 🙎🏻‍♂️

function solution(n, m) {
  return [maxAcommonDivisor(n, m), (n * m) / maxAcommonDivisor(n, m)];
}

function maxAcommonDivisor(a, b) {
  let remainder = 0;

  while (b !== 0) {
    remainder = a % b;
    a = b;
    b = remainder;
  }

  return a;
}

/* 
(풀이)
최대공약수를 구하는 함수를 만들어준다. 함수는
나머지 값을 넣어주는 변수하나를 생성해주고 while 문으로 b가 0이 되면 탈출하게 되는데 이유는

(a가 작을경우)
remainder = a 가 그대로 들어감
a = b a보다 큰값인 b가 들어감
b = remainder 나머지값이 아닌 a가 b에 할당되고 결국 a=b b=a 가 되어 다음
반복부터는 큰값에서 작은값을 나눈 나머지값을 b에 할당하게 된다 이렇게 반복문을 돌다보면
나머지값을 할당받는 b는 맞아떨어질 경우 0 이 되고 그때 나머지를 0 으로 만드는 작은값 b를
할당 받은 a를 리턴해서 받아오면 그값이 최대공약수이다.
최소공배수는 2개의 피연산자 값을 곱한값에 최대공약수를 나눠주면 나온다.

이해는 했는데 알고리즘과 연관하여 풀어가는건 어렵다...

*/

 

참고 풀이 (재귀함수, 함수분리)

function solution(n, m) {
  return [greatestCommonDivisor(n, m), leastCommonMultiple(n, m)];
}
//최대 공약수
function greatestCommonDivisor(num1, num2) {
  const remainder = num1 % num2;
  return num2 === 0 ? num1 : greatestCommonDivisor(num2, remainder);
}
//최소 공배수
function leastCommonMultiple(num1, num2) {
  return (num1 * num2) / greatestCommonDivisor(num1, num2);
}

• 재귀 함수를 이용해 풀어낸 풀이다.
• 함수를 분리해 읽어내기에 훨씬 쉬워보인다.

 

참고 풀이2 (재귀함수, 중첩함수)

function solution(n, m) {
  const gcd = (a, b) => (a % b === 0 ? b : gcd(b, a % b));
  const lcm = (a, b) => (a * b) / gcd(a, b);

  return [gcd(n, m), lcm(n, m)];
}

• 중첩함수를 사용한 풀이다.
• 예전에는 중첩함수를 사용하면 성능상의 이슈가 있었지만 현재는 아무런 문제가 없기에 분리한 함수와 중첩함수 중 목적과 장점을 비교하여 생각하며 코드를 짜도록 노력하자.

 

 

• 재귀함수를 주로 사용하는 알고리즘 등.. 시간 될때 하나씩 찾아서 정리해보자.