티스토리 뷰


최대공약수의 정의
   ===> 최대공약수란 주어지는 두 정수의 약수 중에서 가장 큰 공통되는 약수를 뜻한다.
 
예를들어 280과 30의 약수는
 
280의 약수 : 1, 2, 4, 5, 7, 8, 10, 14, 20, 28, 40, 56, 70, 140, 280
30의 약수 : 1, 2, 3, 5, 6, 10, 15, 30
이다.
 
이중 공통되는 약수는 1, 2, 5, 10이며 그중에 10이 최대공약수(GCD)이다.
 
수학교과서에 나오는 최대공약수를 구하는 방법은 소인수분해를 이용하여 구한다.
 
허나 소인수분해를 이용한 최대공약수를 구하는 방법은 손으로 풀기에는 더할나위 없이 좋지만
 
컴퓨터로 구현하기에는 조금은 껄끄럽다.
 
그래서 유클리드의 알고리즘을 컴퓨터에서 쓴다.
 
유클리드 알고리즘
 
유클리드 알고리즘은 뺄셈과 두 값의 교환으로만 최대공약수를 구할 수 있는 방법이다.
 
A 와 B라는 정수가 있다. 이 A와 B가 최대공약수로서 G를 갖는다고 할때 A와 B는 다음과 같이
 
표현할 수 있다.
 
A = a*G(280=28*10)
B = b*G(30=3*10)
 
위에서 소문자로 쓴 a와 b는 각 A와 B를 G로 나누었을때의 몫을 의미하고 a와 b는 서로소(공통되는 약수가 1밖에 없는경우)이다.
 
그렇다면 A-B와 B의 최대공약수는 얼마일까? 다음식으로 보자.
 
A-B = a*G - b*G = (a-b)*G
 
(a-b)와 b는 역시 서로소이므로 A-B와 B의 최대공약수는 역시 G이다.
 
즉 쉽게 말로 표현한다면 GCD(u, v)라는 함수가 있어 이것이 u와 v의 최대공약수를 구하는 기능을
 
한다고할 때 다음과 같은 성질을 지닌다.
 
GCD(u, v) = GCD(u-v, v)                            식1
GCD(u, v) = GCD(v, u) {순서는 관계없다.}    식2
GCD(u, 0) = u                                            식3
{     만약 u라는 수와 0의 최대공약수는 얼마일까? 0은 어떤수와 곱해도 0이기 떄문에
       0의 약수는 정의상 모든 정수가 된다.(0=u*0  }
 
위 식1, 식2, 식3을 이용해서 280과 30의 최대공약수를 구할 수 있다.
 
이 유클리드 알고리즘을 말로 풀어본다면
 
1. 임의의 두 정수 u와 v를 입력받는다.
2. v가 u보다 크면 v와 u의 값을 교환한다.
3. u에다 u-v의 값을 저장한다.
4.u가 0인가? 0이 아니면 순서2로 돌아간다.
                  0이면 v가 최대공약수이다.
 
이 알고리즘을 그대로 C언어로 작성한다면 다음과 같다.
 
int get_gcd(int u, int v) // 1. 임의의 두 정수 u와 v를 입력받는다.
{
    int t;    
    while(u != 0)  // 4.u가 0인가? 0이 아니면 순서2로 돌아간다.  
    {
        if(v > u)  // 2. v가 u보다 크면 v와 u의 값을 교환한다.
        {
            t = v;
            v = u;
            u = t;
        }
        u = u - v;  // 3. u에다 u-v의 값을 저장한다.
    }
    return v;   // 0이면 v가 최대공약수이다.
}
위 함수는 유클리드 알고리즘을 적용한 함수이다.
 
따로 main함수를 만들어 한번 실행해보도록 하자.
 
모든 알고리즘은 개선될 여지가 있다. 위의 빼기를 이용한 유클리드 알고리즘은 입력되는 두 수
 
u와 v의 차이가 클 때 실행 시간이 오래걸리는 단점이 있다.
 
이를 개선한 방식은 아래와 같다.
 
GCD(u, v) = GCD(u%v, v)            식4
 
a % b == c일때 c는 항상 b보다 작은 성질이 있다. 즉 나머지는 나누는 수보다 작다는것인데
 
이를 이용하면 뺄셈을 이용할 경우 항상 u와 v의 대소비교를 했던 것과는 반대로 %연산을 이용하면
 
대소가 분명해져서 %연산 후 무조건 두 값을 교환하면 되므로 if(u<v)와 같은 문장이 필요가 없다.
 
다음은 나머지 연산을 이용한 알고리즘을 말로 표현해본것이다.
 
1. 임의의 두 정수 u와 v를 입력받는다.
2. v가 0인가?   0이면 u가 최대공약수 이다. 끝
                     0이 아니면 2.1 u에 u%v를 대입한다.
                                     2.2 u와 v의 값을 교환한다.
3. 2로 돌아간다.
 
이 알고리즘을 그대로 C언어로 작성한다면 다음과 같다.

int gcd_modulus(int u, int v)  // 1. 임의의 두 정수 u와 v를 입력받는다.
{
    int t;
    while(v)  // 2. v가 0인가?
    {
        t = u % v;  // 2.1 u에 u%v를 대입한다.
        u = v;   // 2.2 u와 v의 값을 교환한다.
        v = t;
    }
    return u; // 0이면 u가 최대공약수 이다. 끝
}
 
추가적으로 재귀적으로 유클리드 알고리즘을 표현한다면 다음과 같다.
 
int gcd_recursion(int u, int v)
{
    if(v == 0)          // v가 0이라면
        return u;      // u가 최대공약수이다.
    else               // v가 0이 아니라면
        return gcd_recursion(v, u % v);   // 서로 값의 위치를 바꾸어 gcd_recursion()함수의 매개변수에 대입하도록 호출한다.
 
끝.
 

출처 : C로 배우는 알고리즘(이재규 지음)

}