코딩/etc

1) 무엇일까? 유클리드 알고리즘은 두 수의 최대공약수(gcd)를 계산하는 알고리즘 중 하나이다. 유클리드 호제법이라고도 하는데 같은 의미이다. 확장된 유클리드 알고리즘은 특정 a와 b에 대해서 as + bt = gcd(a,b)인 s와 t를 구하는 알고리즘이다. 2) 선후관계 확장된 유클리드 알고리즘은 유클리드 알고리즘을 사용하기 때문에, 유클리드 알고리즘을 먼저 알고 있어야 이해할 수 있다. 3) 유클리드 알고리즘 유클리드 알고리즘은 최대공약수의 두가지 기초 성질을 이용한 알고리즘이다. a(나눠지는 수) = q(몫) * b(나누는 수) + r(나머지) 이라 할 때 (필수조건 : a >= b) 1. gcd(a, 0) = a 이다. 2. gcd(a, b) = gcd (b, r) 4) 유클리드 알고리즘 - ..