수학과의 좌충우돌 프로그래밍

안녕하세요 강민성입니다. 오늘은 유클리드 알고리즘과 그 확장에 대해서 알아보도록 하겠습니다. 유클리드 알고리즘이란? 먼저 유클리드 알고리즘이란 유클리드 호제법이라고도 하며 두 수에 대해서 최대공약수를 구하는 방법입니다. 두 수가 일반적인 방법으로 최대 공약수를 구하기 너무 커졌을 때 이 유클리드 알고리즘을 사용하면 보다 쉽게 구할 수 있습니다. 이제 유클리드 알고리즘을 살펴보면 두 수 a,b에 대해서(a>b), a = q * b + r 라 하면 q 는 몫, r은 나머지가 됩니다. 이 때, gcd(a,b) = gcd(b,r) 이 성립하고 이와 같은 과정을 계속 거쳐 나머지가 0이 되었을 때 나누는 수가 a,b의 최대공약수에 만족하게 됩니다. 예시를 통해서 알아볼까요? 240꽈 46의 최대공약수를 구한다고 ..