코딩테스트/알고리즘1 유클리드 호제법(Euclidean algorithm) 유클리드 호제법이란?유클리드 호제법(Euclidean algorithm)은 유클리드 알고리즘이라고도 불리우며,두 양의 정수 혹은 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 효율적인 알고리즘이다.그리스 수학자 유클리드((Euclid)가 작성한 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라고 한다. 원리GCD(a,b)=GCD(b,amodb) 두 수 a와 b (a>b)의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다.이 과정을 반복하여 나머지가0이 될 때 나누는 수가 두 수의 최대공약수이다. 큰 수인 a를 b로 나눈 나머지 r을 구한다.a를 b로 대체하고, b를 r로 대체한다.나머지 r이 0이 될 때까지 반복한다.나머지가 0이 되었을 때, 나누는.. 2025. 1. 21. 이전 1 다음