Summary
1. 최대공약수와 최소공배수를 유클리드 호제법을 이용하여 구현한다.
이론
[1. 최대공약수 - GCD(Greatest Common Divisor]
두 수가 공통으로 가지고 있는 약수 중 가장 큰 수
= 최대값 / 공통으로 가지고 있는 약수 중에서
[1-1. N이 작은 경우]
[로직 예시 - N이 작은 경우]
12 18 의 최대공약수 구하기
1) 1부터 12 18 중 최솟값 까지 for문을 돌리면서 12 18 과 나누어 떨어지는지 체크
1-1) 만약 두 수 모두 나누어 떨어진다면 최댓값을 저장한다. public static int maxCommonDivision(int n, int m) {
int ans = 0;
for(int i=1; i<=Math.min(n,m); i++) { // 1~ n,m의 최솟값까지
if(n % i == 0 && m % i == 0) { // 두 수가 공통으로 0으로 나누어 떨어질 때
ans = i; // 그 최댓값을 저장한다.
}
}
return ans;
}
하지만, 두 수가 1835813035 과 6894864663 같이 크다면 최소 1835813035번 연산을 해야 하니, 1초 기준 연산 횟수 약 1억 회를 훨씬 초과하게 된다.
[1-2. N이 큰 경우]
이 문제를 해결하기 위해 유클리드 호제법 알고리즘(GCD = Greatest Common Divisor)을 사용한다.
알고리즘은 다음과 같다.
1) 큰 수 % 작은 수
2) 앞 단계의 작은 수 % 앞 단계의 연산 결과
3) 2)를 반복하여 나머지가 0이 되는 순간이 최대공약수
public static long gcd(long a, long remain) {
if(remain == 0) { // 나머지가 0인 경우
return a;
}
return gcd(remain, a % remain);
}
[2. 최소공배수 - LCM(Least Common Multiple)]
두 수에 서로 공통으로 존재하는 배수 중 가장 작은 수
= 최솟값인데 / a,b 둘 다 공통된 배수 중에서
이해가 어렵다면, 이렇게 생각해보자.
위 그림에서 딸은 한 번에 2칸씩 이동하고, 아빠는 한 번에 5칸씩 이동한다면 딸과 아빠를 만나는 지점은 최소 10칸을 가야 만날 수 있다. 이 것이 최소공배수이다.
즉, 10은 2의 배수이기도 하고, 5의 배수이기도 한 수 중에 가장 작은 수이다. = 최소공배수
최소공배수는 a, b 두 수를 곱하고 최대공약수로 나누어주면 된다.
즉, (a*b) / gcd(a,b) 를 하면 된다.
public static long gcd(long a, long remain) {
if(remain == 0) { // 나머지가 0인 경우
return a;
}
return gcd(remain, a % remain);
}
public static long lcm(long a, long b) {
return (a*b)/gcd(a,b);
}
연습 문제
| 코드트리_최대공약수 구하기 | https://www.codetree.ai/missions/5/problems/find-the-greatest-common-divisor/description | #최대공약수, #함수 |
| 코드트리_최소공배수 구하기 | https://www.codetree.ai/missions/5/problems/find-the-least-common-multiple/description | #최소공배수, #함수 |
| ⭐백준_1850번: 최대공약수 | https://www.acmicpc.net/problem/1850 | #최대공약수 변형 응용 |
| ⭐재귀함수를 이용한 최소공배수 | https://www.codetree.ai/missions/5/problems/least-common-multiple-using-recursive-function/description | #여러 개의 입력이 주어지는 최소공배수 |
