[코딩테스트 24일차] BAEKJOON 2609번 : 최대공약수와 최소공배수

[BAEKJOON 2609번 : 최대공약수와 최소공배수]

[문제]

---

[고찰]

해당 문제에 대해서는 아이디어를 생각하지 못해, 풀이를 검색한 후 풀었습니다.

유클리드 호제법으로 문제를 풀었고, 이 개념에 대해 정리해두고자 합니다.

---

[개념]

유클리드 호제법

유클리드 호제법은 큰 수를 작은 수로 나누었을 때의 나머지를 이용해서, 점점 더 작은 수의 쌍으로 문제를 줄여가며 최대공약수를 구하는 방법입니다.

 

유클리드 호제법으로 구하는 최대공약수

유클리드 호제법에서 두 자연수 A, B (A > B)의 최대공약수(GCD)는 A를 B로 나눈 나머지 R에 대해,

GCD(A, B) = GCD(B, R)이고, R이 0이 될 때의 B가 최대공약수가 됩니다.

 

이것이 성립하는 이유는 A와 B의 공약수는 R = A % B와도 공통으로 나누어지기 때문입니다.

 

예를 들어 A가 24이고, B가 18이면, 24 = 18 x 1 + 6 입니다.

여기서 6이 남는 나머지가 되는데, A와 B의 공약수는 이 6에도 반드시 존재합니다.

그래서 GCD(A, B) = GCD(B, A % B)가 성립합니다.

 

최소공배수

최소공배수(LCM)는 두 수의 곱을 최대공약수로 나눈 값입니다.

그렇기에 LCM(A, B) = (A x B) / GCD(A, B)가 성립합니다.

 

A와 B의 공통된 배수 중 가장 작은 수는, A와 B를 곱한 후 공통된 부분(GCD)을 중복 제거해야 최소가 되야하기 때문에 최대공약수로 두 수의 곱을 나눕니다.

---

[정리]

이런 수학적 개념에 대한 부족한 점을 코딩 테스트를 하면서 많이 깨닫는 것 같습니다.

더욱 증진해야겠습니다.

---

[Solution]

#include <iostream>
using namespace std;

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

	return a;
}

int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

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

	cout << gcd(a, b) << '\n';
	cout << lcm(a, b) << '\n';

	return 0;
}