안녕하세요. 오늘은 최대공약수를 구하는 알고리즘을 소개하려고 합니다.사실 키보드 몇 번 치고 금방 찾을 수 있는 간단한 알고리즘이지만, 한 번 생각을 정리하고자 작성합니다.최대공약수를 구하는 알고리즘 중 가장 잘 알려진, 유클리드 호제법을 소개합니다.먼저 최대공약수의 정의부터 짚고 넘어가겠습니다.1. 최대공약수 (Greatest Common Divisor; GCD)$$\text{두 정수의 공약수 중에서 가장 큰 공약수}$$사실 이 정의만으로는 최대공약수를 정의하는데 부족함이 있을 순 있지만, 이해하는 데에는 어려움이 없기에 자세한 정의의 언급은 생략합니다. 2. 유클리드 호제법 (Euclidean algorithm)$$a,b\in ℤ \text{이고, }a\text{를 }b\text{로 나눈 나머지를 }..
