이산수학 보강 수업에서 유클리드 알고리즘에 대해 배웠다. 1학년 때부터 계속 배웠던건데 이번으로 3번째 정도 들으니까 좀 알겠더라.. 유클리드 알고리즘(유클리드 호제법)이란 2개의 자연수의 최대공약수를 쉽게 알아낼 수 있는 알고리즘이다. 최대공약수란 두 정수를 나누어 떨어지게 하는 수 중 가장 큰 정수를 의미한다. 두 정수 A, B의 최대공약수 k를 구해보자 (A > B) A = B * q + r 이라고 할 수 있다. (q는 몫, r은 나머지) A와 B의 최대 공약수는 k이므로 A = k·A', B = k·B' 라고 하자. (A'과 B'은 서로소) 그러면 k·A' = ( k·B') * q + r 이다. 이때, r = k·A' - ( k·B') * q 라고 쓸 수 있다. r = k(A' - B'·q)이므로..
