유클리드 호제법이란?
두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법 중 하나로, 고대 그리스 수학자인 유클리드가 제안한 알고리즘으로, 매우 간단하면서 효과적인 방법
원리?
자연수 a와 b가 있다고 하면, a를 b로 나눈 나머지를 구한다. 나머지를 r이라고 한다.
나머지 r이 0이라면, b는 a와 b의 최대공약수이다. 따라서 알고리즘을 종료하고 b를 결과로 출력한다.
만약 나머지 r이 0이 아니라면, b를 a로 대체하고, r을 b로 대체한다.
다시 말해서 GCD(a, b) = GCD(b, r) 인 것이다.
식으로 풀면, a = bq + r 일 때 GCD(a, b) = GCD(b, r)이다
예시?
48과 18의 최대공약수(GCD)를 구해보면,
1. 48 % 18 = 12 (나머지가 0이 아님)
2. 18 % 12 = 6 (나머지가 0이 아님)
3. 12 % 6 = 0 (나머지가 0임)
따라서 48과 18의 최대공약수(GCD)는 6임을 알 수 있다
또한, GCD(48, 18) = GCD(18, 12) = GCD(12, 6) 임도 알수 있다.
결론
유클리드 호제법은 매우 효율적이며, 큰 수의 최대공약수 계산에도 적합하다.
큰 수들의 계산을 작은 수들의 계산으로 축소해 나가면서 결론적으로는 작은수들의 계산으로 최대공약수를 구할 수 있는 것이다.
응용
최대공약수는 물론, 최소공배수도 구할 수 있다
최소공배수(LCM, Least Common Multiple)은 다음과 같은 공식을 활용하여 풀이할 수 있다
LCM(a, b) = (a*b) / GCD(a, b)앞서 예시에서 GCD(48, 18) = 6임을 알았으므로 이를 이용하여 최소공배수도 구해보도록 하겠다
간단하게 식에 대입하면 48*18/6 = 48*3 = 144 이므로, 두 수의 최소공배수(LCM)은 144임 또한 알 수 있다
댓글