코딩 연습

유클리드 알고리즘 이 글을 이해하기 위해서는 유클리드 알고리즘을 먼저 이해해야 합니다. 다음 동영상을 참고하시기 바랍니다. 확장 유클리드 알고리즘 $x, y$ 에 대한 부정방정식 $ax+by=c$ 는 $c$ 의 값이 ${\rm gcd}(a, b)$ 의 배수일 때만 정수해를 갖는다고 알려져 있다. 즉, $ax+by=c$ 가 정수해를 갖는 $c$의 최솟값이 ${\rm gcd}(a, b)$ 가 되는 것이다. 따라서 확장 유클리드 알고리즘은 말 그대로 유클리드 알고리즘을 확장하여 $a, b$ 의 최대공약수 뿐만 아니라, $ax+by={\rm gcd}(a, b)$를 만족하는 정수해 $x, y$ 도 구하는 알고리즘이라고 생각하면 된다. $240$ 과 $46$ 의 최대공약수를 $c={\rm gcd}(240, 46)$..