[알고리즘] 최대공약수 구하기 - 유클리드 호제법 Euclidean Algorithm

 

일반적으로 A와 B의 최대공약수를 구하는 가장 쉬운 방법은

A와 B를 2부터 A와 B중 더 작은 수 까지 모든 자연수로 나누는 것이다.

이 방법은 수가 커질수록 시간이 오래걸려 비효율적이며, 모든 수로 나눠야 하므로 시간복잡도는 O(n)이 된다.

이때 유클리드 호제법을 사용한다.

 

유클리드 호제법 (Euclidean Algorithm) :

두 정수의 최대공약수(Greatest Common Divisor)를 구하는 알고리즘

 

A > B 일 때1. A % B = C2. B % C = D3. 위 과정을 계속 반복4. X % Y = 0, Y가 A와 B의 최대공약수

 

그림으로 표현해 보자

두 정수 A, B를 직사각형의 두 변의 길이라고 생각하면 직사각형을 정사각형으로 완전히 채우려고 할 때 정사각형의 가장 긴 변의 길이를 구하는 문제로 바꿀 수 있다

   1. 짧은 변의 길이를 한 변으로 하는 정사각형으로 채운다

   2. 남은 직사각형에 대해 반복

 

예를들어 22와 8의 최소공배수를 구할 때

22 = 8 + 8 + 6  /  8 = 6 + 2  /  6 = 2 + 2 + 2  => 22와 8의 최소공배수는 2

 

22와 8의 최소공배수를 구하는 과정

 

 

메서드 gcd() : 자연수 a와 b 두 수의 최대공약수 찾기

매개변수 : int a, int b

반환값 : a와 b의 최대공약수 반환

 

- 재귀함수를 사용해 구현한 경우

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	} else {
    	int c = a % b;
		return gcd(b, c);
	}
}

 

- 반복문으로 구현한 경우

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

 

 

 

 

유클리드 호제법 Euclidean Algorithm : O(logN)