GCD (1) 썸네일형 리스트형 44. Euclidean Algorithm 유클리드 호제법(유클리드 알고리즘, Euclidean Algorithm)은 두 다항식의 최대공약다항식을 빠르게 구하는 알고리즘이다. 일반적으로 차수가 1 이상인 두 다항식의 최대공약다항식을 구하는 상황은 자주 발생하지 않으며 대부분 차수가 0인 두 다항식, 즉 두 정수의 최대공약수를 구하기 위해 유클리드 호제법을 이용하게 된다. 유클리드 호제법의 내용은 다음과 같다. gcd(a,b)는 a와 b의 최대공약다항식을 의미한다.a, b가 다항식이고 a를 b로 나눈 나머지를 c라고 하면 gcd(a,b)=gcd(c,b)이다. (b≠0) 유클리드 호제법의 증명은 다음과 같다. 더보기a, b가 a≥b≥0.. 이전 1 다음
