[ALG] 유클리드 호제법(Euclidean algorithm)

유클리드 호제법이란?

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 유클리드 호제법을 정리하기 전, 최대공약수와 최소공배수의 개념을 먼저 정리 후 단계를 밟아가자.

 

 

최대공약수(GCD)

두 수 이상의 여러 수의 공통된 약수를 의미하며, 두 수 이상의 여러 수의 공약수 중 최대인 수를 가리킨다.

//최대 공약수
let num1 = 30;
let num2 = 18;

let gcd = 1;
let cdArr = [1, ];

let funcGCD = (nu1, nu2) => {
    for (let i=2; i<=Math.min(nu1, nu2); i++) { 
        //두 수의 공통된 약수를 찾아야 하기에 두 수중, 작은 값을 기준으로 한다.
        if (nu1 % i === 0 && nu2 % i === 0) { 
            //for문을 수행하며 nu1, nu2의 나머지가 0이 되었다는 것은 두 수의 공통된 약수를 의미한다.
            gcd = i; //최대공약수

            cdArr.push(gcd); //공약수 배열
        }
    }
    return gcd;
}

funcGCD(num1, num2); // 6
cdArr; // [ 1, 2, 3, 6 ]

 

최소공배수(LCM)

공배수(common multiple)란 두 수 이상의 여러 수의 공통된 배수를 의미하며, 두 수 이상의 여러 수의 공배수 중 최소인 수를 가리킨다.

//최소 공배수
let num1 = 15;
let num2 = 10;

let lcm = 1;

let funcLCM = (nu1, nu2) => {
    while(true) { 
        //주어진 두 수의 공통된 배수를 구해야 하기 때문에, 배수를 찾은 즉시 break 되도록 설정한다.
        if (lcm % num1 === 0 && lcm % num2 === 0) { 
            //변수 lcm을 나눈 두 수의 나머지가 0일 때, 최소공배수이다.
            break;
        }
        lcm++; //조건문을 만족하지 않을 시, 값을 증가시키며 찾는다.
    }

    return lcm;
}

funcLCM(num1, num2); // 30

 

유클리드 호제법

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘이다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

*정리하자면, GCD(num1, num2) = GCD(num2, r)이다.

r을 나머지라 가정하고 num1과 num2의 나머지는 GCD(num2, r)이 된다는 것이다.

//유클리드 호제법
let num1 = 24, 
    num2 = 16;

euclidean = (nu1, nu2) => {
    while(nu2 > 0) {
        // nu2이 0보다 클 때 조건이 성립되며, 주어진 두 수를 나누어 나머지를  
        let r = nu1 % nu2;
        nu1 = nu2;
        nu2 = r;
        //나머지 값을 변수 r에 넣어 스왑 과정을 진행한다.
    }

    return nu1;
}

euclidean(num1, num2); // 8

 

참고 사이트

유클리드 호제법 - 위키백과, 우리 모두의 백과사전