컴공댕이 공부일지
[ 정수론 ] 최대공약수 구하기 - 유클리드 호제법 본문
유클리드 호제법이란?
두 양의 정수의 최대공약수를 구하는 알고리즘 중 하나로,
두 수가 반복적으로 서로 나누어지면서, 나머지를 구하며 최대공약수를 얻게 된다.
유클리드 호제법의 기본 원리
📝 A,B의 최대공약수 = A-B, B의 최대공약수
* GCD : 최대 공약수( Greatest Common Divisor )
아하 ! 그러면 A, B의 최대공약수를 구하는 대신, A-B, B를 이용하면 빠르겠군 !
그런데 A와 B의 차가 크다면 ...?
가령, 1024와 2라고 해보자.
GCD (1024, 2)
GCD (1022, 2)
GCD (1020, 2)
GCD (1018, 2)
.
.
.
GCD (2, 2)
이걸 어느 세월에....ㅜ
그래서 나온 또 다른 증명 !
📝 A,B의 최대공약수 = A%B, B의 최대공약수
위에서 증명했듯 "A, B의 최대공약수"와 "A%B, B의 최대공약수"가 같으므로,
두 수를 나눈 나머지를 활용하면 최대공약수를 빠르게 구할 수 있다.
이러한 원리에 기반한 알고리즘이 바로 유클리드 호제법이다.
알고리즘
유클리드 호제법의 알고리즘은 다음과 같다.
위에서 증명한 GCD(A%B, B) = GCD(A, B) 인 점을 활용하는 것이다.
A, B의 최대공약수를 구하려한다. ( A>B>0 )
1) A%B를 B자리에, B를 A자리에 넣고 반복합니다. ( A%B < B )
2) 작은 수인 B가 0이 될때까지 위의 과정을 반복한다.
3) B가 0이 되었을 때, A 자리에 있는 수가 두 수의 최대공약수이다.
숫자로 예시를 들어보면, 4와 18의 최대공약수를 구해보자.
GCD(18, 4) = GCD(4, 2) = GCD(2, 0)
이런식으로 나머지연산과 스왑을 반복하면 두 수의 최대공약수가 2라는 것을 구할 수 있다.
구현
그럼 유클리드 호제법으로 최대공약수를 구하는 c++ 코드를 작성해보자.
주로 재귀를 사용하고, 반복문으로도 구현이 가능하다 :)
// 재귀
int gcd_recursive(int a, int b) {
if (b == 0) {
return a; // b가 0이면, a가 최대공약수 !
}
return gcd_recursive(b, a % b);
}
// 반복문
int gcd_iterative(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a; // b가 0이면, a가 최대공약수 !
}
'CS > 알고리즘' 카테고리의 다른 글
[ 동적프로그래밍 ] 개념 (피보나치, 외발뛰기) (0) | 2024.04.02 |
---|---|
[ 탐욕법 ] 그리디 알고리즘의 사용 조건 및 정당성 증명, 예시 문제 풀이 (1) | 2024.03.28 |
[ 비트마스킹 ] 비트마스킹의 정의와 예제 문제 풀이 ( c++ 백준 11723 집합 ) (0) | 2024.03.12 |
[ 정수론 ] 소수 구하기 - 에라토스테네스의 체, 제곱근 기준 소수 판별, 구현까지 (3) | 2024.03.05 |
[ 정렬 알고리즘 ] 퀵 정렬 java (0) | 2023.03.31 |