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

유클리드 호제법 (유클리드 알고리즘)은 두 수의 최대공약수를 구하는 알고리즘이다.  호제법이란 두 수가 서로 상대방 수를 나눠 결국 원하는 수를 얻는 알고리즘이다.

 

유클리드 호제법을 이해하기 위해서는 MOD 연산에 대해 알아야 한다

MOD 연산이란? 

두 값을 나눈 나머지를 구하는 연산! 

 

예로, 1112와 695의 최대공약수를 구해보자

먼저, 큰 수를 작은 수로 나눈 나머지를 구한다. (MOD 연산 수행)

1112 MOD 695 = 417

 

그 후, 나눴던 수와 나머지로 또 MOD 연산을 한다.

695  MOD 417 = 278

이 과정을 계속 반복한다!

417 MOD 278= 139
278 MOD 139 = 0

 

나머지가 0이 됐을 때, 마지막 계산에서 나누는 수로 사용된 숫자 139가 1112와 695의 최대공약수가 된다!

 

 

1) 반복문을 이용해 최대공약수 구하기

int gcd(int a, int b) { 
    while(b!=0) {
      int r=a%b;
      a=b;
      b=r;
    }
    return a;
 }

 

 

2) 재귀함수를 이용해 최대공약수 구하기

 * 재귀함수란? 정의 단계에서 자신을 재참조하는 함수

int GCD(int a, int b) {
	if(a%b ==0) {
		return b;
	}
	return GCD(b, a%b);
}

재귀함수를 이용하면 구현이 간단하고 코드가 간결해지며 시간 복잡도는 0(logN)

 

 

+) 최소공배수 구하기

두 수의 곱 / 두 수의 최대 공약수

int lcm(int a, int b) { //최소공배수
	//L=A*B/G
	//0이 아닌 두 수의 곱 / 두 수의 최대 공약수
	return a*b / gcd(a,b);
}