유클리드 호제법에 대한 쉬운 설명과 증명

유클리드 호제법 정도의 유명한 알고리즘은 위키백과 정도만 봐도 잘 설명되어 있는데, 조금 더 간결한 설명을 원하시는 분들을 위해서 글을 써보기로 했어요. 인터넷에선 수학적으로 너무 잘 설명된 글이나 아니면 증명 없이 코드만 박아둔 글이 많아서요;;; 유클리드 호제법은, (적어도 우리가 일반적으로 알고리즘 문제를 풀 때에는,) 두 자연수의 최대공약수를 빠르게 구하기 위해 이용되는 알고리즘이에요. 쪼끔 더 문자를 써서 표현하자면, 두 자연수 A, B의 최대공약수 G를 빠르게 구하기 위해서 이용하며, A>B일 때 G(A, B)와 G(A%B, B)가 같다는 점을 이용해요. 코드는 아래와 같겠죠. int gcd(int a, int b) { if (a < b) swap(&a, &b); return b != 0 ? ..

2023.03.18