[Do it! 알고리즘 코딩테스트: Chapter 7. 정수론] 유클리드 호제법(Euclidean Algorithm)

본 포스팅은 Do it! 알고리즘 코딩테스트: C++편을 토대로 공부한 내용을 정리하기 위한 포스팅입니다.

https://github.com/KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp

GitHub - KwonKiHyeok/Do_it_Alogrithm_Coding_Test_with_Cpp: Do it! 알고리즘 코딩 테스트: C++편

 

 

7-3 유클리드 호제법(Euclidean-Algorithm)

 유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수(GCD, Greatest Common Divisor)를 효율적으로 구하는 알고리즘이다. 2천 년 전 고대 그리스 수학자 유클리드가 그의 책 Elements에서 소개한 방법으로, 현재까지도 널리 사용된다.


두 수 a와 b의 최대공약수를 구하고자 할 때, gcd(a, b) = gcd(b, a mod b) (단, a > b)

여기서 a mod  b는 a를 b로 나눈 나머지이다.
이 과정을 나머지가 0이 될 때까지 반복하면, 그때의 b가 두 수의 최대공약수이다.

증명

  a > b인 두 양의 정수 a, b가 있다고 가정한다. 이때 두 수의 최대 공약수를 G라고 하면, a, b는 아래와 같이 표현할 수 있다.

 

 G를 최대 공약수라고 했으므로 A와 B는 서로소임을 알 수 있다. 

 a > b라고 가정했으므로 a는 아래와 같이 표현할 수 있다. 이때 q는 a를 b로 나눈 몫이고 r은 나머지이다.

 위의 식에 a = AG, b = BG를 대입하면 아래와 같이 식을 나타낼 수 있다.

 b의 정의에 따르면 b = BG이고, 나머지인 r과 b 사이에는 G라는 공통의 약수가 생기게 됨을 알 수 있다.

 만약 유클리드 호제법이 참이라면 G가 최대공약수가 되어야 한다. 그리고 G가 최대 공약수임을 증명하는 것은 A-qB와 B는 서로소임을 증명하는 것과도 같다.

 

 여기서 귀류법을 사용하여 A-qB와 B는 서로소가 아니라는 사실이 틀렸음을 증명한다.('A-qB와 B는 서로소이다.' = 'A-qB와 B는 서로소가 아님이 틀렸다.')

 

 두 수가 서로소가 아니라고 가정했으므로 1보다 큰 최대공약수인 t가 존재한다고 생각할 수 있다.

 여기서 B = nt를 대입해보면 아래와 같은 식을 얻을 수 있고, 이 식을 변형시키면 모순이 발생하게 된다.

 

 

 처음에 A와 B는 서로소라고 가정했는데 지금 A와 B가 t라는 공통의 약수를 갖게 됨을 확인할 수 있다. 이는 처음 가정의 모순임을 알 수 있고 따라서 A-qB와 B는 서로소이다. 

 

 

정리하면 a>b인 두 양의 정수 a,b에 대하여, a=qb+r(나머지 r은 0 이상 b 미만,q는 몫)이라 하면, gcd(a,b)=gcd(b,r) (a,b의 최대공약수=b,r의 최대공약수)이다.​

​

알고리즘 흐름

1. 큰 수를 작은 수로 나누는 mod 연산을 수행한다.
2. 앞 단계에서의 작은 수와 mod 연산 결괏값(나머지)으로 mod 연산을 수행한다.
3. 단계 2를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.

 

// Baekjoon Online Judge Problem. 1934

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	int a, b;
	cin >> T;

	for (int i = 0; i < T; i++) {
		cin >> a >> b;

		int temp_a = a, temp_b = b, c = 0;

		while (a != 0 && b != 0) {
			if (a > b) {
				a %= b;
			}
			else {
				b %= a;
			}
		};

		if (a == 0)
			c = b;
		else
			c = a;

		cout << c * (temp_a / c) * (temp_b / c) << '\n';
	}

	return 0;
}

 

// Baekjoon Online Judge Problem. 1850

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long A, B;
	cin >> A >> B;

	while (A != 0 && B != 0) {
		if (A > B)
			A %= B;
		else
			B %= A;
	}

	if (A > B) {
		for (long long i = 0; i < A; i++)
			cout << '1';
	}
	else {
		for (long long i = 0; i < B; i++)
			cout << '1';
	}
	
	return 0;
}