프로그래머스 Lv 1. 최대공약수와 최소공배수

GCD (최대공약수)

두 수 A와 B의 공통된 약수 중에서 가장 큰 정수.

• 가장 구하기 쉬운 방법은 2부터 두 수 중 최소값(min(a,b)) 까지 모든 정수로 나누어보는 것.

let GCD = (num1, num2) => {
	let gcd = 1;
    for(let i = 2; i <= Math.min(num1, num2); i++){
    	if(num1 % i === 0 && num2 % i === 0){
        	gcd = i;
        }
    }
    return gcd;
}

• 유클리드 호제법
  기본 원리는 num1을 num2로 나눈 나머지를 r이라고 할때, GCD(num1, num2) = GCD(num2, r)과 같다.
  r이 0이라면, 그 때의 num2는 최대공약수이다.

GCD(24, 16) = GCD(16, 8) = GCD(8, 0) // GCD = 8

재귀하여, GCD 산출

let getGCD = (num1, num2) => (num2 > 0 ? getGCD(num2, num1 % num2) : num1);

재귀하지 않는다면, 시간 복잡도가 0으로 구현할 수 있다.

let getGCD = (num1, num2) => {
	while(num2 > 0){
    	let r = num1 % num2;
        num1 = num2;
        num2 = r;
    }
    return num1;
}

LCM (최소공배수)

두 수, 혹은 그 이상의 여러 수의 공통인 배수 중 가장 작은 수.

• 가장 구하기 쉬운 방법은 lcm을 1부터 시작해 lcm++, 각 두 수를 lcm으로 나누었을 때, 나머지가 0인지를 비교한다.

let LCM = (num1, num2) => {
	let lcm = 1;
    while(true){
    	if((lcm % num1 === 0) && (lcm % num2 == 0)){
        	break;
        }
    lcm++;
    }
    return lcm
}

• 유클리드 호제법
  위 GCD에 대한 호제법을 응용해 구할 수 있다.

lcm = gcd * (num1 / gcd) * (num2 /gcd)
lcm = (num1 * num2) / gcd
//이는 num1 * num2 = gcd * lcm의 원리를 이용하는 것.

문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

제한 사항
두 수는 1이상 1000000이하의 자연수입니다.

나의 풀이

function solution(num1, num2) {
    var answer = [];
    answer.push(get(num1, num2), (num1 * num2) / get(num1, num2))
    return answer;
}

function get(num1, num2){
    while(num2 > 0){
        let r = num1 % num2;
        num1 = num2;
        num2 = r;
    }
    return num1
}

get 함수를 통해 GCD를 구해, 최대공약수와 최소공배수를 산출

다른 사람의 풀이

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

for문을 사용하되, 일반적인 사용이 아니었다.
초기값 자리에, 변수 선언. ab = a * b로 하여, 조건 자체를 r = a % b로