유클리드 알고리즘

최대공약수(Greatest Common Divisor) : 주어지는 두 정수의 약수 중에서 가장 큰 공통약수

ex) 280 과 30 의 GCD는 10이다.

. 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

- 소인수분해를 통해 GCD를 구할 수 있다.

2  |    280      30
5  |    140      15
     ---------------
           28       3

최대공약수 = 2 * 5 = 10

 

GCD 관련 법칙

- GCD(u,v) = GCD(u-v, v) if u > v

- GCD(u,v) = GCD(v, u)

- GCD(u,0) = u

 

위 법칙으로 아래와 같은 알고리즘을 구성할 수 있다.(유클리드 알고리즘)

 

임의의 두 정수 u, v에 대해

(1) v의 값이 u보다 크다면 v와 u를 바꾼다.

(2) u  = u - v

(3) u가 0이 아니면 (1)로 돌아감, 0이면 v가 최대공약수

 

예로 확인해보자.

ex) u = 280, v = 30
GCD(280, 30) = GCD(250,30)
                       = GCD(220,30)
                       = GCD(190,30)
                       = GCD(160,30)
                       = GCD(130,30)
                       = GCD(100,30)
                       = GCD(70,30)
                       = GCD(40,30)
                       = GCD(10,30)
                       = GCD(30,10)
                       = GCD(20,10)
                       = GCD(10,10)
                       = GCD(0,10)
                       = 10

 

위 알고리즘을 코드로 구현하면 아래와 같다.(실행해 보려면 아래 우측 상단의 아이콘 선택)

원본 코드

#include <iostream>
#include <string>

int get_gcd(int u, int v);

int main()
{  
  int u, v;
  int gcd;
  
  u = 280;
  v= 30;
  
  std::cout << "get_gcd result " << "\n";
  gcd = get_gcd(u,v);
  std::cout << "gcd =  " << gcd  << "\n";
  
}

int get_gcd(int u, int v)
{
    int t;
    while (u)
    {
         if(u < v)
         {
             t = u; u =v; v = t;
         }
         u = u- v;
    }
    return v;
}

알고리즘 개선

문제점 : 뺄셈기반 알고리즘의 문제 :  u와 v의 값 차이가 클 때 많은 뺄셈을 요구한다.

 

. 뺄셈의 결과는 나눗셈의 나머지를 구하는 것!!

 - GCD(u,v) = GCD(u%v, v) = GCD(v, u%v)

 - u%v < v

 

위 법칙으로 아래와 같은 알고리즘을 구성할 수 있다.

 

임의의 두 정수 u, v에 대해

(1) v 가 0이 아니면

  (1.1) u = u%v

  (1.2) u와 v를 교환

(2) v가 0이면 u 가 GCD,   v가 0이 아니면 (1)로 돌아감

 

예로 확인해 보자

ex) u = 30, v = 280
GCD(30, 280) = GCD(30, 280)
                       = GCD(280, 30)
                       = GCD(10, 30)
                       = GCD(30, 10)
                       = GCD(0, 10)
                       = GCD(10, 0)
                       = 10

 

위 알고리즘을 코드로 구현하면 아래와 같다.(실행해 보려면 아래 우측 상단의 아이콘 선택)

 

원본 코드 

#include <iostream>
using namespace std;
 
int get_gcd(int u, int v)
{
    int t;
    while (u)
    {
         if(u < v)
         {
             t = u; u =v; v = t;
         }
         u = u- v;
    }
    return v;
}
 
int gcd_modules(int u, int v)
{
	int t;
	while(v) // v가 0보다 클 동안
	{
		t = u % v;
		u = v;
		v = t;
	}
	return u;
}
 
int gcd_recursion(int u, int v)
{
	if (v == 0)
		return u;
	else
		return gcd_recursion(v, u%v);
}
 
int main()
{  
  int u, v;
  int gcd;
 
  u = 280;
  v= 30;
 
  std::cout << "get_gcd result " << "\n";
  gcd = get_gcd(u,v);
  std::cout << "gcd =  " << gcd  << "\n";
 
  std::cout << "gcd_modules result " << "\n";
  gcd = gcd_modules(u,v);
  std::cout << "gcd =  " << gcd  << "\n";
 
  std::cout << "gcd_recursion result " << "\n";
  gcd = gcd_recursion(u,v);
  std::cout << "gcd =  " << gcd  << "\n";
 
 
  return 0; 
}