728x90
반응형
유클리드 호제법 (euclidean - algorithm)
두 수의 최대공약수 구하는 알고리즘
핵심이론: MOD 연산: 두 값을 나눈 나머지를 구하는 연산
1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
2. 앞 단계에서 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행한다.
3. 2를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대공약수로 선택한다.
def GCD(x , y):
min_num = min(x, y)
max_num = max(x, y)
if min_num == 0:
return max_num
else:
return GCD(min_num, max_num%min_num)
반응형
