[C++]최대공약수 구하기(3가지 방법, 유클리드 호제법)

문제

최대 공약수 구하기

 

두 정수 a, b의 최대공약수를 구하는 함수 get_gcd()를 구현해보세요.

int get_gcd(int a, int b)
{
	// 두 정수 a, b의 최대공약수를 구하는 함수를 구현할 것!
}

int main()
{
	int gcd = get_gcd(26, 48);
	cout << gcd << endl;
}

 

 

 

문제풀이

 

(1) [1, min(a, b) ] 범위에서 두 수 모두의 약수가 되는 값 중 최댓값을 구하는 방법 

  * 가장 단순하고 직관적인 방법

int get_gcd(int a, int b)
{
	int max_div = 1;	// 가장 큰 공약수를 저장할 변수
	int range = min(a, b); 	// 두 수 중 작은 값까지만 조사

	// i부터 공약수를 찾는다.
	for (int i = 1; i <= range; i++)
	{ 
		// 두 수 모두의 약수일 경우
		if (a % i == 0 && b % i == 0)
		{ 
			max_div = i; 	// 갱신 (i는 점점 증가하므로 range 끝까지 수행)
		}
	}
	
    return max_div;
}

▶ 이는 두 정수 a, b에 대하여 O(min(a,b))의 시간 복잡도를 가짐

알고리즘 코딩시험에서 최대공약수를 구하는 문제를 이렇게 푼다면, 분명히 시간초과가 발생할 것이다. 조금 더 빠르게 할 수 없을까?  

 

 

(2) 역순 탐색

[1, min(a, b)]부터 1까지 역순으로 탐색하여 가장 처음 발견된 공약수가 결국 최대 공약수가 됨

 

int get_gcd(int a, int b)
{
	int max_div = 1; // 가장 큰 공약수를 저장할 변수
	int range = min(a, b);// 두 수 중 작은 값까지만 조사
	
	// i부터 공약수를 찾는다.
	for (int i = range; i >= 1; i--)
	{ 
		 // 두 수 모두의 약수일 경우
		if (a % i == 0 && b % i == 0)
		{
			max_div = i; // 저장 후 탈출
			break; // i는 점점 감소하므로, 더이상 볼 필요가 없다.
		}
	}
	
    return max_div;
}

 

 ▶ 일반적인 경우에는 (1)보다는 빠르겠지만 최악의 경우(두 정수 a, b가 서로 소인 경우)에는 동일하게 모든 수를 검사하므로 결국 (1)과 같은 시간 복잡도를 보임

 

 

 

3) 유클리드 호제법

 

f(a, b) = gcd(a, b)라 하자.

이 때 a mod b = 0 이라면, f(a, b) = b임이 자명.

이 때 a mod b이 0이 아닌 경우, f(a, b) = f(b, a mod b)가 성립한다. 

이를 유클리드 호제법이라고 함

 

// (1) 반복문을 이용한 방법
int gcd(int a, int b) 
{ 
	int mod = a % b;
    
	while (mod > 0)
	{
		a = b;
		b = mod;
		mod = a % b;
	}
	
    return b;
}

 
// (2) 재귀 함수형
int gcd2(int a, int b)
{ 
	if (a % b == 0) 
    	return b;
	else 
    	return gcd2(b, a % b);
}


// (3) 삼항 연산자 축약형
int gcd3(int a, int b)
{ 
	return (a % b == 0 ? b : gcd3(b, a % b));
} 

  ▶  정수 a와 b에 대하여 근사적으로 O( log2(min(a, b)) ) 시간복잡도를 가짐