[알고리즘] 유클리드 호제법(Euclidean algorithm)

유클리드 호제법이란?

두 수의 최대공약수(GCD)를 구하는 알고리즘으로, 유클리드에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다.

유클리드 호제법 동작 과정

유클리드 호제법에는 모듈러 연산(나머지 연산)이 사용된다.

• 큰 수를 작은 수로 나눈 나머지를 구한다.
• 나눴던 수와 그 나머지로 또 모듈러 연산을 한다.
• 위의 과정을 반복하다가 나머지가 0이 되었을 때, 마지막 연산에서 나누는 수로 사용된 수가 최대공약수(GCD)이다.

cf) 이 알고리즘의 포인트는 두 수가 모두 GCD의 배수라는 점이다. 그렇기 때문에 나머지 연산의 반복으로 GCD를 구할 수 있다.

'''
1. 최대공약수(Greatest Common Divisor)
숫자 2개 입력받고 최대공약수를 구하는 일반적인 방법
2부터 둘중 작은 수 까지 나누었을 때 나눠지는 수 중 가장 큰 수

32 16 -> 16
24 16 -> 8
'''
answer=0
a,b=map(int,input())
for i in range(2,min(a,b)+1):
    if a%i==0 and b%i==0:
        answer=i
print(answer)

'''
2. 최대공약수를 위 코드보다 조금 더 빠른 속도로 구하고 싶을 때
유클리드 호제법(최초의 알고리즘라는 것에 의미가 있음)
'''

a,b=map(int,input())
answer=0
while b:
    answer = a % b
    a = b
    b = answer
print(a)
'''
최소공배수(Least Common Multipe)
a와 b의 최소공배수는 GCD를 먼저 구한 다음에
LCM = a*b/GCD 이렇게 구한다.
'''

💡유클리드 호제법 활용 문제

• 프로그래머스 N개의 최소공배수