javascript 두 수의 최대공약수와 최소공배수 구하기

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환

나의 풀이

function solution(n, m) {
    var answer = [];
    var gcd = 1;
    
    for (let i = 1; i <= Math.min(n, m); i++) {
        if (n % i === 0 && m % i === 0) {
            gcd = i;
        }
    }
    var lcm = (n * m) / gcd;
    
    answer.push(gcd, lcm);
    
    return answer;
}

• gcd (공약수) 변수를 1로 초기화한다
• for문을 사용하여 1부터 n/m중 더 작은 수까지 반복한다 n과 m이 인덱스 i로 모두 나누어 떨어지면 gcd 변수를 업데이트
• lcm 공배수 계산은 n과 m을 곱한 후 최대공약수 gcd로 나눈다

 

다른 풀이

1) 유클리드 알고리즘

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

• 변수 r 선언 : r이라는 변수를 선언하여 두 수 a와 b를 나눌 때 발생하는 나머지 값을 저장한다
• for문 : GDC를 계산하는 핵심 부분으로 유클리드 알고리즘의 핵심 아이디어를 활용한다
  • ab = a * b : ab변수에 a와 b의 곱을 저장 
  • r = a % b :  현재의 a를 b로 나눈 나머지를 r 변수에 저장
  • a = b : a 변수에 b 값을 대입
  • b = r; : b 변수에 r 나머지값을 대입
  • for 루프의 조건은 r값이 0이 아닐 때까지 계속 실행
  • 유클리드 알고리즘에서 GCD를 찾을 때 나머지가 0이 되는 순간 이전 단계의 b 값이 최대 공약수가 된다 (GCD) 
• 공약수('b")와 공배수(ab/b)를 배열로 묶어서 반환

아무리 봐도 .. 이해가 안된다 .. !  예시로 들어보자 a = 3이고 b = 22일때

• 초기 상태 a = 3, b = 22
• ab 값 계산 : a.* b = 66
• r 값 계산 : a % b = 3 나머지가 0이 아니므로 for 루프 실행
• a = b : a = 22 // b = r : b = 3
• r 값 계산 : a % b = 22 % 3 = 1 나머지가 0이 아니므로 for 실행 
• a = 3 / b = 1
• r 값 계산 : a % b = 3  %  1 = 0 나머지 0이 되어 for 종료
• b : 최대공약수 1 
• ab / b : 66 / 1 = 최대공배수 66 

2) 재귀 

function greatestCommonDivisor(a, b) {return b ? greatestCommonDivisor(b, a % b) : Math.abs(a);}
function leastCommonMultipleOfTwo(a, b) {return (a * b) / greatestCommonDivisor(a, b);}
function gcdlcm(a, b) {
    return [greatestCommonDivisor(a, b),leastCommonMultipleOfTwo(a, b)];
}

•  gCD (최대공약수) 
  • 두 수 a와 b의 최대공약수를 재귀적으로 계산
  • b가 0이 될 때까지 a를 b로 나눈 나머지를 계산하고 나머지가 0이 되면 a의 절대값을 반환 
  • 그렇지 않으면 b과 a % b를 인자로 재귀 호출하여 GCD 계산
• LCM (최소공배수)
  • 두 수의 곱을 최대공약수로 나눈 것