[알고리즘] 유클리드 호제법

2009. 05. 04 (月)

유클리드(B.C. 365 ~ B.C.300)는 기하학의 아버지라고 불리는 유명한 고대 수학자 그 중 가장 유명한 것이 13권으로 구성된 기하학 원본 그 책은 그 선배인 피타고라스 플라톤 히포크라테스등의 연구한 여러 가지의 자료를 정선하고 거기에 자신의 창작을 가미하여 조직적인 교과서로 편찬한 것으로 수학사상 최고의 성전 이라 할 수 있음

 

 

1.     최대공약수(GCD : Greatest Common Divisor)란

 

-       정수 a, b의 약수 중에서 공통된 약수를 공약수라 하며 공약수중 가장 큰 수를 최대 공약수라고 한다.

 

-       최대공약수를 구하기 위해서는 다음과 같은 과정을 거쳐야 한다.

 

1.      정수 a의 약수로 구성된 집합 A를 구한다.

2.      정수 b의 약수로 구성된 집합 B를 구한다.

3.      정수 a와 b의 공약수로 구성된 집합 C를 구한다(집합 A와 집합 B의 교집합)

4.      집합 C에서 가장 큰 수인 c가 정수 a와 b의 최대공약수이다.

 

-       한계점

 

1.      정수와 약수를 구하는데 그 값이 매우 큰 경우에는 많은 시간이 걸린다.

2.      A 집합과 B 집합의 교집합을 구해서 공약수 집합인 C를 만드는데 시간이 오래 걸린다. A와 B 집합의 모든 요소들을 비교해서 같은 값을 찾는 작업이 집합내의 요소의 수가 많은 경우에는 많은 시간을 필요로 한다.

3.      공약수의 집합인 C에서 최대공약수인 C를 찾는데 대소 비교를 통해 가장 큰 수를 찾아야 하므로 많은 시간이 소요된다.

 

 

 

2.     유클리드 알고리즘

 

-       유클리드 호제법이라고도 불리우는 이 알고리즘은 주어진 서로 소가 아닌 두 수 a, b에 대해 최대공약수를 찾는 것으로 다음 두 규칙을 전제로 하고 있다.

 

1.     b 가 a로 나눠서 떨어지면 두 수의 최대공약수는 b 이다.

2.     a 를 b로 나눴을 때 나머지가 r이면, 두 수의 최대공약수는 r과 b의 최대공약수와 같다.

3.      

-       Ex) 1804 와 328의 최대공약수 구하기.

 

1.     1804를 328로 나누었을 때의 나머지 r은 164 이다.

2.     다음으로 328과 164의 최대공약수를 구한다. 328을 164로 나누었을 때의 나머지는 0이므로 최대공약수는 164 이다.

 

-       Ex) 120과 50의 최대공약수 구하기

 

1.     120을 50으로 나누었을 때의 나머지 r 은 20이다.

2.     다음으로 50과 20의 최대공약수를 구한다. 50을 20으로 나누었을 때의 나머지는 10이다.

3.     다음으로 20과 10의 최대공약수를 구한다. 20을 10으로 나누었을 때의 나머지는 0이므로 최대공약수는 10이 최대공약수 이다.

 

3.     소스

#include "stdafx.h"

#include <stdio.h>

 

int InputData();

 

int _tmain(int argc, _TCHAR* argv[])

{

 

        printf("============= 유클리드호제법==============\n");

        printf("최대공약수를구하려는두수를입력하시요\n");

 

        int a, b;

 

        printf("a = ");

        a = InputData();

        printf("b = ");

        b = InputData();

 

        int i = 0;

              

        while(b != 0)

        {

               i++;

               int c = b;

               b = a%b;

               a = c;

               printf("[%d]step (%d, %d)\n",i, a, b);

        }

 

        printf(" GCD = %d\n" , a);

       

        return 0;

}

 

int InputData()

{

        int i;

        scanf("%d", &i);

        return i;

}