[알고리즘, 원리] 유클리드 호제법
정의 a = bx+r 일 때 (a,b) = (b,r) a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다. 이를 이용하여 반복하면 두 수의 최대공약수를 쉽게 구할 수 있다. 구현 파이썬 (Python) def gcd(a,b): while b != 0: a, b = b, a%b return a 두 수에서 유클리드 호제법을 반복하여 최대공약수를 구하는 함수 def gcd(a, b): r = b % a if r == 0: return a return gcd(r, a) 재귀 함수를 이용한 구현 def gcd(*num_list): if len(num_list) == 1: return num_list[0] elif len(num_list) == 2: a, b = num_list[0], num_l..
2022. 9. 10.
