알고리즘 정리 #1 - 최대공약수와 최소공배수

최대공약수(GCD, Gratest Common Divisor)

---

최대공약수란, 2개의 자연수의 공통된 약수 중에서 가장 큰 정수이다.

 

여기서 약수는 어떤 수를 나누었을 때 나누어 떨어지는 수이다.

-> 6의 약수는 1, 2 ,3, 6이다.  

만약 1과 자기 자신밖에 약수가 존재하지 않으면 '소수'이다.

-> 7, 11 등등

 

따라서 두 자연수의 약수 중에 공통된 최댓값을 구하면 된다. 

-> 두 자연수 2와 4의 최대공약수(GCD)는 2이다.(2의 약수 1, 2와 4의 약수 1,2,4)

 

최대공약수를 구하는 여러 알고리즘 중에 유클리드 호제법(Euclidean Algorithm)이 가장 유명하다.

호제법 또는 연제법(連除法)은 두 수 A와 B가 있으면 서로의 수를 나누어가기를 반복하며 나머지가 0이 되었을 때의 나누는 수가 A와 B의 최대공약수이다.

 

유클리드 호제법 공식으로 소스코드로 구현해보면 다음과 같다.

int GCD(int a, int b){
    if (b == 0) { //2. b가 0이면 a를 return한다.
        return a;
    }
    else {
        return GCD(b, a%b);//1. a를 b로 나눈 나머지가 b의 인자로 입력된다(재귀 호출)
    }
}

함수 GCD는 재귀함수로 구성되어있다.

먼저, 두 정수를 입력받고 (int형의 a와 b)

b가 0이 아니면 a를 b로 나눈 나머지를 b에 넣고 다시 GCD를 호출하며 반복한다.

 

만약 최대공약수를 구할 때까지(b=0) n번을 반복한다면 이 함수의 시간 복잡도는 빅오 표기법으로 O(n)이다.

 

 

 

최소공배수(LCM, Least Common Multiple)

---

최소공배수란, 2개의 자연수의 공통된 배수 중에서 가장 작은 정수이다.

최소공배수는 공통된 배수 중에서 가장 작은 정수를 의미한다.

 

5와 15의 최소공배수를 찾아보면,

5의 배수 5 10 15 20 25 ....

15의 배수 15 30 45 60 ....

따라서, 공통인 최솟값은 15이다.

 

최소공배수를 구하는 공식은 여러 가지가 있지만, 일반적으로 두 자연수의 최대공약수에 서로소까지 곱하면 된다.

우리는 아까 위에서 최대공약수를 구하는 법을 알아냈다. 그렇다면, 두 수의 서로소를 구해서 곱해주면 된다.

최대공약수(LCM) = 최대공배수(GCD) * 입력값들의 서로소
 

 

두 수의 서로소는 어떻게 구할까?

입력값 a의 서로소 = 입력값 a / a와b의 최대공약수
입력값 b의 서로소 = 입력값 b / a와b의 최대공약수

 

따라서, 최대공약수(LCM)를 구하는 방법은 아래와 같다.

 

최대공약수(LCM) = 최대공약수(GCD) * (a/최대공약수(GCD)) * (b/최대공약수(GCD))
 

 

이 방법을 소스코드로 코드화 하면 아래와 같다.

 

int GCD(int a, int b){
    if (b == 0) { 
        return a;
    }
    else {
        return GCD(b, a%b);
    }
}
int LCM(int a, int b){
    int g = GCD(a,b);
    return g * (a/g) * (b/g);
}