백준 9613 #유클리드호제법 #최대공약수 #GCD

[Algorithm] 최대공약수(Gcd) : 유클리드 호제법 원리

#유클리드 호제법 유클리드 호제법이란 두 자연수 사이의 최대공약수(Gcd)를 구하는 알고리즘 중 하나이다. 두 자연수 a, b(a>b)에 대하여 a를 b로 나눈 나머지를 r이라고 하자. 그러면 Gcd(a, b) = Gcd(b, r)와 같고, r = 0이 될때까지 이 과정을 반복했을때 b의 값이 두 수의 최대공약수가 된다. #예시 두 수 1248과 462의 최대공약수를 유클리드 호제법을 이용하여 구해보자. a = 1248, b = 462라 하면 1248 = 462 * 2 + 324 이때 Gcd(1248, 462) = Gcd(462, 324)이고, 다시 a= 462, b = 324라 하면 462 = 324 * 1 + 138 마찬가지로 Gcd(462, 324) = Gcd(324, 138)이다. 이 과정을 r ..