1. 유클리드 호제법이란❓
최대공약수를 구하는 알고리즘으로 기원전 300년 경에 쓰여진 유클리드의 원로에 적혀있으며, 인류 최초의 알고리즘 이라고 한다.
2. 이해하기💡
유클리드 호제법으로 최대공약수를 구하는 방법은 아주 간단한다. 다음 2가지만 기억하면 된다.
1. 두 수의 자리를 바꿔가며 모듈러 연산을 한다.
2. 1. 과정을 나머지가 0이 나올 때 까지 반복한다.
3. 36과 60의 최대공약수 구하기
a = 36, b = 60
a = a % b // a = 36
a <-> b // a와 b의 값 바꾸기
a = 60, b = 36
a = a % b // a = 24
a <-> b // a와 b의 값 바꾸기
a = 36, b = 24
a = a % b // a = 12
a <-> b
a = 24, b = 12
a = a % b //나머지가 0이 되었다!이때 나누는 값이 12이므로 최대공약수는 12가 된다.
4. 최소공배수 구하기
최대공약수를 알고있다면 최소공배수를 구하는건 정말 간단하다.
최소공배수 = a * b / (최대공약수)
36와 60의 최소공배수를 구해보자
a = 36, b = 60
최소공배수 = 36 * 60 / 12
답 : 180
5. 최대공약수, 최소공배수 java 코드
반복문과 재귀함수로 구현 가능하지만, 재귀함수가 훨씬 간결하여 사용하기 편하다.
//최대공약수
private static int gcd(int a, int b) {
if(b == 0) return a;
else return gcd(b,a%b);
}
//최소공배수
private static int lcm(int a, int b) {
return a*b/gcd(a,b);
}관련 문제
글을 마치며
알고리즘을 공부하면 맨날 까먹어서 정리하기 위해 올리는데, 간단한 알고리즘인데도 글로 쓰려니 생각보다 쉽지않다.
유클리드 호제법은 다시 볼일 없길 바라며.. 😥
💖