유클리드 호제법 (Euclidean Algorithm) in C
2022. 8. 3. 01:23ㆍSTUDY/알고리즘
반응형
유클리드 호제법은, 두 정수의 최대 공약수(Greatest Common Divisor)를 구하는 알고리즘 중 하나이다.
a, b의 최대 공약수는, a/b를 나눈 나머지인 r과 b의 최대공약수와 같다는 성질에 따라, 재귀와 반복문을 통해 구현할 수 있다.
* 최대 공약수 ( Greatest Common Divisor, GCD )
두 개 이상의 수가 공통으로 갖고 있는 약수 중 가장 큰 ! 수.
ex)
8의 약수 : 1, 2, 4, 8
12의 약수 : 1, 2, 3, 4, 6, 12
8과 12의 최대 공약수 : 4
* 최소 공배수 ( Least Common Multiple , LCM )
ex)
3의 배수 : 3, 6, 9, 12, 15 ...
5의 배수 : 5, 10, 15, 20 ...
3과 5의 최소 공배수 : 15
좀 더 구체적으로, 비교대상의 2개의 자연수 a와 b 에서, ( 단 a > b ) a를 b로 나눈 나머지를 r이라고 했을 때,
GCD(a, b) = GCD(b, r) 과 같고,
" r이 0이면 그 때 b가 최대 공약수이다! " 라는 원리를 활용한 알고리즘이다.
ex)
GCD( 24, 16 ) -> GCD( 16, 8 ) -> GCD( 8, 0 ) : 최대 공약수 = 8
GCD( 55, 22 ) -> GCD( 22, 11 ) -> GCD( 11, 0 ) : 최대 공약수 = 11
# 재귀 함수 활용
#include <stdio.h>
int Euclidean(int a, int b)
{
if(b == 0) return a;
else return Euclidean(b, a%b);
}
int main(void)
{
printf("%d\n", Euclidean(11, 10);
return 0;
}
# 반복문 활용
#include <stdio.h>
int Euclidean(int a, int b)
{
while(1) {
int r = a%b;
a = b;
b = r;
if( b == 0) break;
}
return a;
}
int main() {
printf("%d\n", Euclidean(11,10));
return 0;
}
# 다항식 활용
int a = 8;
int b = 16;
int c = 24;
int result = GCD(a,b);
result = GCD(result, c);
printf("%d\n", c);
# 장점 : 빠르다 ! 일반적으로는 일일히 나눠줘야하는 O(N)인데 유클리드 호제 쓰면 시간 복잡도가 O(logN) 이다.
# 단점 : 최대 공약수는 빠르게 산출이 가능한데, 최소 공배수를 계산함에 있어서는 좀 다르기 때문, !
# 최소 공배수 구하기
int LCM(int a, int b)
{
return a * b / GCD(a,b);
}
GCD를 구하는 알고리즘을 먼저 유클리드 호제법을 활용하여 구현한 뒤에,
a * b / GCD( a, b ) 를 해주면 최소 공배수를 구할 수 있다!
728x90
반응형
'STUDY > 알고리즘' 카테고리의 다른 글
백준 설탕배달 (0) | 2022.08.16 |
---|---|
Two Pointer (C++) (2) | 2022.08.11 |
점근적 표기법 ( asymptotic notation) (0) | 2022.08.02 |
Adjacency list in C (0) | 2022.07.30 |
About Graph & BFS,DFS (0) | 2022.07.18 |