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