글을 시작하기 전에
velog는 내가 평소 UX와 UI가 예쁘고 편하다고 생각했던 블로그 중 하나였다.
나의 첫 블로그, 첫 글을 velog를 통해 만들 수 있어서 기분이 좋다.
이 글을 시작으로 velog에서 많은 사람들과 소통할 수 있었으면 좋겠다.
🙏 만약 잘못된 부분이 있거나, 부족한 부분이 있다면 댓글로 알려주세요!
유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘
이다.
유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다.
호제법이란? 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다.
일반적으로 최대공약수를 구하기 위해선 먼저 소인수분해
를 해야한다.
1112 = 139 X 2 X 2 X 2
695 = 139 X 5
두 수를 소인수분해한 후, 공통된 소수를 찾으면 된다. 이를 통해 두 수의 최대공약수(GCD)는 139
인 것을 알 수 있다.
이 방법은 수가 커질수록 소인수분해하기 어려워진다는 단점이 있다.
이때, 유클리드 호제법을 사용하면 조금 더 효율적으로 최대공약수(GCD)를 구할 수 있다!
💡 유클리드 호제법을 이해하기 위해서는 MOD연산에 대해 알고 있어야 한다.
MOD연산이란? 두 값을 나눈 나머지를 구하는 연산!
먼저, 큰 수를 작은 수로 나눈 나머지를 구한다. 즉, MOD 연산을 한다.
1112 mod 695 = 417
그 다음, 나눴던 수와 나머지로 또 MOD 연산을 한다.
695 mod 417 = 278
이 과정을 계속 반복한다.
417 mod 278 = 139
278 mod 139 = 0
나머지가 0이 됐을 때, 마지막 계산에서 나누는 수로 사용된 139
가 1112와 695의 최대공약수
가 된다.
간단하게 말하면, 유클리드 호제법은 MOD연산을 반복하면 된다!
어떻게 유클리드 호제법으로 최대공약수(GCD)를 구할 수 있을까?
1112와 695를 막대의 길이로 표현한 뒤에, 두 수의 최대공약수 N으로 나눠보았다.
위에서 우리는 최대공약수가 139라는 것을 알았기 때문에 8칸, 5칸으로 나누었지만 실제로는 모른다고 생각하면 된다.
하지만, 1112와 695가 최대공약수 N의 배수라는 것은 알고 있다.
위에서 한 대로, 1112와 695를 반복해서 MOD 연산한다.
이 그림을 통해 연산 중에 나온 나머지
417, 278, 139도 모두 N의 배수인 수라는 것과 같은 최대공약수를 가진다는 것을 알 수 있다.
278은 139로 나누어지므로 나머지가 0이 된다.
이때, 최대공약수 N이 139라는 것을 알 수 있다.
유클리드 호제법은 나눗셈만 반복해서 최대공약수(GCD)를 구할 수 있다.
두 개의 수가 아무리 커도 정해진 순서로 계산하면 효율적으로 최대공약수를 구할 수 있다.
[참고] 알고리즘도감, [그림] 자체제작
유클리드 호제법은 반복문과 재귀함수를 통해 쉽게 표현할 수 있다.
C언어로 간단하게 작성해봤다. (조건: a>b
)
int GCD(int a, int b){
int tmp;
while(b){ //b가 0이 될 때까지
tmp = a % b;
a = b;
b = c;
}
return a;
}
int GCD(int a, int b){
return b ? GCD(b, a % b) : a;
}
유클리드호제법을 이용하여 해결할 수 있는 알고리즘 문제다.
글을 마치며
처음 글을 쓰면서, 글을 쓰는 것이 생각보다 더욱 어렵다는 것을 알게 되었다.
그동안 내가 읽었던 글을 쓰신 분들께 너무나 감사하다😢
앞으로 운영체제, 알고리즘 등 내가 알게된 것들을 여러 사람들과 나눌 수 있었으면 좋겠다.
잘보고가요!