목록Algorithm (1)
기억하기보단 기록하자
최대공약수 알고리즘(유클리드)
유클리드 최대공약수 수학자로 유명한 유클리드(Euclid)는 최대공약수에 다음과 같은 성질이 있다는 것을 발견하였다. a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같습니다. 즉, gcd(a, b) = gcd(b, a%b)입니다. 어떤 수와 0의 최대공약수는 자기 자신입니다. 즉, gcd(n, 0) = n입니다. 더보기 ex) 1. 60과 24의 최대공약수 gcd(60, 24) = gcd(24, 60%24) = gcd(24, 12) = gcd(12, 24%12) = gcd(12, 0) = 12 2. 81과 27의 최대공약수 gcd(81, 27) = gcd(27, 81%27) = gcd(27, 0) = gcd(27, 0) = 27 a와 b의 최대공약수를 구하기 위해서 (a, b)..
Algorithm
2021. 4. 4. 17:09