[알고리듬] #49 유클리드 법

파이썬 실습창을 열 수 있습니다.실습창 열기

Euclid

 

 

문제

양의 정수 2개를 입력 받아서 최대공약수(GCD)와 최소 공배수(LCM)을 구하여 보세요.

 

1. 문제 분석(problem analysis)

•  60의 약수는 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60 이며,
   36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 입니다.
   60과 36에 공통으로 있는 공약수는 1, 2, 3, 4, 6, 12 이며,
   가장 큰 공약수 즉, 최대 공약수(GCD: Greatest Common Divisor)는 12입니다.
•  또한,
   60의 배수는 60, 120, 180, 240, 300, 360, 420, 480 등이며,
   36의 배수는 36, 72, 108, 144, 180, 216, 252, 288, 324, 360, 396 등입니다.
   60과 36에 공통으로 있는 공배수는 180, 360 등이며,
   가장 작은 공배수 즉, 최소 공배수(LCM: Least Common Multiple)는 180입니다.
    
   60과 36의 최소 공배수는 60과 36을 곱한 값을 최소 공배수로 나누면 쉽게 구할 수 있습니다.
   60*36/12=180입니다. 식으로 만들면, LCM= A*B / GCD 가 됩니다.

2. 알고리듬 설계(algorithm design)

LCM과 GCD를 쉽게 구하는 방법이 있습니다.

위의 그림에 있는 209와 969를 예로 들겠습니다.

1) 209를 969로 나눈다. (몫은 0, 나머지는 209이다)
2) 969를 209로 나눈다. (몫은 4이며, 나머지는 133이다)
3) 나머지가 0이 될 때까지 위의 과정을 반복한다.
    위의 경우는 57을 19로 나누어 나머지가 0이 되었으므로 종료한다.
4) 최대 공약수(GCD)는 나머지를 0이 되게 한 수이다. 위의 경우는 19가 최대 공약수이다.
5) 최소공배수(LCM)은 209 * 969 / 19를 계산한 10659 이다.

이러한 방법을 유클리드 법(Euclid's algorithm)이라고 합니다.
유클리드는 이 방법을 생각한 사람인데, 기원전 300년경의 그리스 사람입니다.

 

• 60과 36의 최대공약수(gcd)와 최소공배수(lcm)를 수작업으로 구할 수 있습니까?
  구할 수 있을 때, 아래를 읽으세요.
•  반복되는 성질을 느꼈습니까?
   어떻게 반복됩니까?
    60이 있던 곳에 36이 가고, 36이 있던 곳에 60을 36으로 나눈 나머지가 가고,
   이러한 과정이 반복 되지요?
   다시 한 번 느끼세요. 느낀 다음에 아래를 보세요.
•  언제 끝이 납니까?
   나머지가 0일 때 종료되지만, 한번 더 진행하면 코딩이 단순하여 집니다.
   36이 있던 원래의 자리에 0이 있으면, 그 때 60이 있던 곳의 값이 최대공약수입니다.

정리합시다.

위의 작업과 비교하며 분석하세요.

• a를 b로 나눈 나머지를 구한다.(몫은 사용되지 않으므로 구하지 않는다)
• a는 b, b는 r로 바꾸어 위의 과정을 반복한다.
• b가 0이 되면 그 때의 a가 최대공약수(gcd)이다. b는 반드시 0이 된다.
• 최소공배수(lcm)는 원래의 a*b를 최대공약수(gcd)로 나누어 구한다.

한번 더 정리하면,

1.  b가 0이면 a가 gcd이다.
2.  b가 0이 아니면 a에는 b, b에는 'a를 b로 나눈 나머지'를 할당한다.
3. (1)의  과정부터 반복한다.

3. 코딩하기(coding)

코딩하여 보세요.

a,b=map(int,input().split())
t=a*b
while b!=0:
    a,b=b,a%b
gcd=a
lcm=t//gcd
print(gcd,lcm)

※ [참고] 함수와 재귀호출에 의한 코딩

함수를 사용한 코딩입니다.

def euclid(a,b):
    while b!=0:
        a,b=b,a%b
    return a    

a,b=map(int,input().split())
gcd=euclid(a,b)
lcm=a*b//gcd
print(gcd,lcm)

 

 재귀호출(recursive call) 전략을 사용한 코딩입니다.

def euclid(a,b):
    if b==0:return a
    return euclid(b,a%b) 

a,b=map(int,input().split())
gcd=euclid(a,b)
lcm=a*b//gcd
print(gcd,lcm)

 

 

수고하셨습니다.

점점 전문가가 되어가고 있습니다.

안녕!