목록유클리드 호제법 (1)
cyphen156
알고리듬#1 최대공약수와 최소공배수 : 유클리드 알고리즘
흔히 유클리드 호제법(Euclidean algorithm)으로 알려진 두 양의 정수의 최대공약수와 최소공배수를 빠르게 찾아내는 문제해결방법이다. 수식이 조금 난잡해서 보기 불편한데 함수 수식으로 변환하면 f(x) = ax + b가 성립한다면 gcd(a, b) = gcd(r, b)이다 GDC(greatest common divisor/최대공약수) 최대공약수를 구하는 일반적인 방법은 다음과 같다. 두 수를 소인수 분해하여 서로 공통되는 약수들을 찾아 모두 곱한다. A = 100, B = 12일 때 두 수의 약수들은 각각 (1, 2, 4, 5, 10, 20, 25, 50, 100), (1, 2, 3, 4, 6, 12)로 1 * 2 * 4 = 8이다. 코드로 약수를 찾아가는 과정은 다음과 같다 아래의 코드는 한..
컴퓨터공학/알고리듬
2024. 2. 14. 15:11