유클리드 호제법 썸네일형 리스트형 Euclidean Algorithm 컴퓨터 사이언스나 컴퓨터 공학을 전공하는 학생이라면 누구나 Euclidean Algorithm을 한 번 쯤을 들어봤을 것이다. Euclidean Algorithm은 가장 오래된 알고리즘 중 하나로 2300년전 그리스의 수학자 Euclid에 의해 고안되었다. Euclidean Algorithm은 음이 아닌 두 정수 a, b의 최대공약수 GCD(a, b)를 구하는 알고리즘으로 C++로는 아래와 같이 간단하게 구현할 수 있다. int GCD(int a, int b){if (b==0) return a;return GCD(b, a%b);} 코드가 워낙 간단하기 때문에 여태껏 그냥 외워서 쓰고 있었는데 사실 그 본질에 대해서는 제대로 이해하고 있지는 않았다. 오늘 우연히 루프 불변식에 대한 복습을 하다가 그 증명을.. 더보기 이전 1 다음
