[알고리즘] 최대공약수, 최소공배수 (유클리드 호제법)

1. 최대 공약수

최대공약수, 최대공배수를 사용하려면 소인수분해를 사용해야 합니다.

하지만 숫자가 크면 클수록 소인수분해의 횟수는 점점 증가하기 때문에 유클리드 호제법을 사용하면 시간복잡도는 단축이 됩니다.

유클리드 호제법은 명시적으로 기술된 가장 오래된 알고리즘으로, 무려 기원전 300년에 쓰여졌다고 합니다.

여기서 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타냅니다.

 

일반적으로 최대공약수를 구하는 가장 쉬운 방법은 2부터 모든 정수로 나누어 보는 방법이 있을 것 같은데 이의 경우 모든 정수를 나눠야 하므로 시간 복잡도는 O(N)이 됩니다.

유클리드 호제법을 사용한다면 때 a % b이 0이 될 때까지 반복을 해주기 때문에 시간 복잡도를 O(Log N)으로 줄일 수 있어 좀 더 효율적인 알고리즘을 작성할 수 있습니다.

 

쉽게 요약하자면, 두 수를 나누어서 나머지를 구한다음 그 나머지로 계속해서 나눠주는 방법 입니다.

 

재귀함수

function gcd(a, b){
	return b ? gcd(b, a%b) : a;
}

    // 삼항연산자를 사용함으로 b가 자연수일때는 true, 0 일때는 false로 입력된다.
    // b가 자연수일때 gcd(b, a%b) 실행, b가 0이되었을 경우 a를 출력한다.

예를 들어 a= 10과 b = 8의 최대 공약수를 구한다고 하면

10과 8을 나누면 나머지가 2가 나오게 되고

재귀함수에 의해 그 다음으로 a= 8과 b = 2를 나눈 나머지가 0이 나오게 되면서 a = 2와 n= 0이 출력이 되고

나머지가 b = 0이 되면서 a = 2가 최소공약수가 되어 집니다.

 

반복문

function gcd(a, b){
	while(b>0){
    	let c = b;
        b = a % b;
        a = c;
        }
	return a;
}

이런식으로 반복문을 사용하여 나타낼 수도 있습니다.

 

2. 최소 공배수

최소 공배수는 최대 공약수를 이용하여 쉽게 구할 수 있습니다.

최소공배수 = 0이 아닌(자연수)  두 수의 곱/ 두 수의 최대공약수

 

결국 최소공배수는 최대공약수를 이용하여 구할 수 있기 때문에 다른 방법을 사용하지 않아도 됩니다.

 

// 최대 공약수
function gcd(a, b){
	return b ? gcd(b, a%b) : a;
}

// 최소 공배수
function lcm(a, b){
	return (a * b) / gcd(a, b)   
}

 

 

위와 같이 최소공배수를 구하기 위해서는 최대공약수 알고리즘을 가져오면 됩니다.

이부분이 단점이라면 단점인 것 같습니다. 최소공배수를 얻기 위해 최대공약수를 구하는 알고리즘이 필요하기 때문입니다.

 

 

 

 

다른 코드

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

리턴문 배열 앞이 최대공약수, 최소 공배수 입니다. 반복문을 특이하게 사용해서 기록합니다.