백준/유클리드 호제법
-
2609 최대공약수와 최소공배수백준/유클리드 호제법 2022. 6. 26. 19:21
1. 유클리드 호제법 설명 1) 최대공약수 : GCD a, b : 정수 r = a mod b (즉, a에 b를 나눈 나머지) 이때 0 ≤ r GCD(a,b) = GCD(b,r) 즉, a와 b의 최대공약수 = b와 r의 최대공약수 예제에 나온 24, 18 에 대해서 최대공약수를 구해보자 단계 1 a = 24, b = 18 => r= 6 GCD(24,18) = GCD(18,6) 단계 2 a = 18, b = 6 => r = 0 r 이 0보다 크거나 같아야 하므로 여기서 멈춘다. r= 0 이라는 뜻은, 18을 6으로 나눈 나머지가 0이라는 것이다. 즉, 18이 6으로 나누어 떨어진다는 것이다. 때문에 6이 18과 6의 최대공약수가 된다. GCD(18,6) = GCD(6,0..