알고리즘
[알고리즘] GCD 최대공약수 구하기 알고리즘
레옹
2022. 4. 29. 06:00
1. 유클리드 알고리즘(Euclidean algorithm)
두 자연수의 최대 공약수(greatest common divisor)를 찾는 알고리즘을 뜻한다.
2. 유클리드 알고리즘 원리
두수 A와 B(A>B)가 있고 A를 B로 나누었을때 나머지가 C일 때
C가 0일경우 B가 최대 공약수이고 아닐경우 A = B 로 B = A % B로 하고 반복해서 C가 0일 될때까지 하면 된다.
ex) GCD(12, 8) -> GCD(8, 4) -> GCD(4, 0) 최소공배수 = 4
장점
- 최대공약수를 구하는 방법중 가장 간단한 방법인 1부터 min(A,B)까지 순서대로 찾는 방법의 시간 복잡도는 O(N)이지만 유클리드 호제법을 이용할 경우 O(Log N)으로 줄일 수 있다.
3. 구현(C/C++)
반복문을 통한 GCD 구하기
int GCD(int a, int b) {
int c;
while (b != 0) {
c = a % b;
a = b;
b = c;
}
return a;
}
재귀함수를 이용한 GCD 구하기
int GCD(int a, int b) {
return b == 0 ? a : GCD(b, a % b);
}
4. 최소공배수 구하기
int LCM(int a, int b) {
return a * b / GCD(a, b);
}
참고