최대공약수와 최소공배수

algorithm/basic with js

최대공약수와 최소공배수

그라파나 2023. 3. 18. 11:29

알고리즘 공부하면서 초등학교 수학으로 돌아가는 경우가 종종 발생했다.

그 중에 하나가 바로 최대공약수와 최소공배수였다.

최대 공약수, GCD : Greatest Common Divisor

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

4와 2의 최대공약수는 무엇일까?

직관적으로 1초만에 답이 나온다. 2다.

왜냐하면 2는 4를 나눌 수 있는 가장 큰 약수이며, 2는 자기 자신을 약수로 하기 때문이다.

몸(?)은 이미 알고 있다. 하지만 이걸 코드로 구현하자니..

pseudo code에 대해 생각해보기로 했다.

1. 숫자를 2개 받아야 한다.

2. 루프를 돌며 각각의 수를 나누어서 둘다 나머지가 0이 되는 '약수'를 먼저 찾는다.

3. 그중에서 가장 큰녀석을 도출한다.

+추가적으로 생각해봐야할 것.

4. 100과 10이 있다고 생각해보자.

숫자가 10이 넘어간 순간 의미가 없어진다. (11은 10보다 크다.)

따라서 둘중 작은수까지만 도달하는 것이 의미가 있다. 작은 수를 가려야 한다.

또한, 다른 하나의 수 (작은 수)는 그 수의 약수가 될 수 있다. 즉,10까지는 루프를 돌아야 한다.

최대공약수 구하는 방법 javascript

let getGCD = (num1, num2) =>{
    // 모든 수의 최소공약수는 1. 일단 초기화.
    // cf. 초기화할때 늘어나면 가장 작은수를 초기화. 
    // 줄어들면 가장 큰 수를 초기화한다. 
    let gcd = 1;
    // 따라서 루프를 돈다면 2부터 시작.
    
    //약수를 담을 배열을 선언.
    let divisors  = [];
    
    // 둘중 작은수에 도달할때까지 for문을 돌아야 한다. 
    // Math.min으로 작은수로 범위를 가린다.
    // 다른 하나의 수가 약수인 경우까지.
    // cf.그경우는 다른 하나의 수가 최대공약수가 된다.
    for (let i = 2; i <= Math.min(num1,num2); i++){
        // 그 둘의 나머지가 0인 경우 i는 그 수의 약수이다.
        // for문을 끝까지 돌면 그 둘의 최대공약수가 도출된다.
        if(num1 % i === 0 && num2 % i === 0){
            gcd = i;
            divisors.push(i);
        }
    }
    //약수들이 쭉 나온다.
    console.log(divisors);
    
    //그중에서 가장 마지막에 들어간 약수가 최대공약수다.
    gcd = divisors[divisors.length-1];
    return gcd;
}
// 시간복잡도는 O(N)이다.

최소 공배수, LCM : Least Common Multiple

두 수의 A와 B의
공통인 배수 중에
가장 작은 정수

3과 4의 최소공배수는 무엇일까?

직관적으로 1초만에 답이 나온다. 12다.

왜냐하면 3과 4는 서로소이다. 공통된 약수가 없다. 따라서 이경우엔 둘이 곱하면 답이 나온다.

역시나 몸(?)은 이미 알고 있다...

pseudo code에 대해 생각해보기로 했다.

1. 숫자를 2개 받아야 한다.

2. 루프를 돌며 각각의 수를 나누어서 둘다 나머지가 0이 되는 수를 찾을때까지 돈다.

3. 그중에서 가장 작은 녀석을 찾는 것이기때문에 찾으면 그 순간 끝이다.

4. 하지만 이 루프는 언제끝날지 모른다. 범위가 지정되어있지 않다. 찾으면 종료한다.

+추가적으로 생각해봐야할 것.

5. 3과 4가 있다고 생각해보자.

각각 구구단을 해야한다. 3과 4의 구구단이 겹치는 지점을 찾아야 한다.

1부터 천천히 하나씩 올라가면서 그 수를 찾아야 한다.

찾은 수는 3으로도 4로도 나누어 떨어진다. 즉, 나머지는 0이다.

최소공배수 구하는 방법 javascript

let getLCM = (num1, num2) =>{
    let lcm = 1;
    //언제끝날지 모르기때문에 while로 돈다. 
    //break할때까지 돌아야 한다.
    while(true){
        //lcm으로 나눈 나머지가 둘다 0일때 그 수가 최소공배수다.
        if((lcm % num1 == 0) && (lcm % num2 == 0)){
             //찾는 즉시 종료한다.
             break;   
        }
        //최소공배수가 될 녀석을 찾을때까지 증가해야 한다.
        lcm++;        
    }
    return lcm;
}
// 시간복잡도는 O(N)이다.

구하는 방법은 알았으나 이것은 개념에 불과했다.