[Algorithm] 백준(BOJ) - 2609. 최대공약수와 최소공배수 (JAVA) / 유클리드 호제법 알고리즘
최대공약수와 최소공배수
두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
Example
#1
입력
24 18
출력
6
72
어떻게 푸는게 좋을까?
최대 공약수 (Gratest Common Divisor)
최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.
최소 공배수 (Least Common Multiple)
최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.
최소공배수 = 두 자연수의 곱 / 최대공약수
유클리드 호제법
유클리드 호제법 알고리즘을 사용하면 최대 공약수를 빠르게 계산할 수 있다.
유클리드 호제법의 정리는 다음과 같다.
2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. - wikipedia
위 내용을 정리해보자.
a, b ∈ ℤ 이고, r = a mod b 이라고 한다. (r은 a에 b를 나눈 나머지를 의미)
이 때, r은 (0 ≤ r < b) 이고, a ≥ b 이다.
a와 b의 최대공약수를 (a, b)라고 할 때, (a, b)의 최대 공약수는 (b, r)의 최대 공약수와 같다.
즉, (a, b) = (b, r) 가 성립한다는 뜻이다.
예를 들어, 두 수 1071, 1029 가 있다고 가정해보자.
(1071, 1029) 일 때, r=42이다.
즉, (1071, 1029) = (1029, 42) 이다.
(1029, 42) 일 때, r=21 이고, (1029, 42) = (42, 21) 이다.
(42, 21) 일 때, r=0 이고, (42, 21) = (21, 0) 이다.
나머지가 0이라는 것은 공통된 약수로 나누어 떨어진다는 의미이므로 최대공약수는 7이 된다.
즉, (1071, 1029) = (1029, 42) = (42, 21) = (21, 0) = 21 처럼 쓸 수 있다.
그리고 GCD(A, B) = d 라고 한다면 A와 B는 각각 다음과 같이 나타낼 수 있다.
이를 알고리즘으로 구성하자면 다음과 같다.
- While 반복문 방식 - 시간 복잡도 O(n)
int gcd(int a, int b) { int mod = a % b; while(mod > 0) { a = b; b = mod; mod = a % b; } } - 재귀 방식 - 시간 복잡도 O(logN)
int gcd(int a, int b) { if (a % b == 0) return b; } else { return gcd(b, a % b); } }
최소 공배수를 구하는 방법은 더 간결하다.
두 수 a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다.
즉, 아래와 같이 알고리즘을 구성할 수 있다.
- 최소공배수
int lcm(int a, int b) { return (a * b) / gcd(a, b); }
내가 작성한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
int a = Integer.parseInt(str[0]);
int b = Integer.parseInt(str[1]);
System.out.println(gcd(a, b));
System.out.println(lcm(a, b));
}
// 최대공약수
private static int gcd(int a, int b) {
int mod = a % b;
while (mod > 0) {
a = b;
b = mod;
mod = a % b;
}
return b;
}
// 최소공배수
private static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
}
reference
더 많은 알고리즘 문제 풀이는 여기서 확인할 수 있다.
댓글남기기