최대공약수 알고리즘

 

Greatest Common Divisor

 

 

Problem	임의의 자연수 n, m (단, n > m) 에 대한 최대공약수?
Input	자연수 n, m
Output	Largest D s.t  n % D and m % D == 0

s.t: Search That의 약자.

 

[1] n-gcd  가장 생각하기 쉬운 알고리즘.

 

n - gcd (n,m)

D <- min(n, m)

while ( D % n != 0 or D % m != 0 )

D <-- D-1

return D

 

간단 설명: 최대 공약수는 두 수중 가장 작은수보다 작거나 같아야하므로

D <- min(n, m)

D를 1씩 감소시키며 n과 m을 모두 나누어 떨어지게 하는 수에서 멈추면

최대 공약수를 리턴한다.

 

구데기인 이유

n= 100000000001 m= 100000000000 이면 연산을

총 100000000000회 수행..컹s

느낌 너무없어

-> 느린 알고리즘은 좋은 알고리즘이 아니다!

 

[2] Euclid Algorithm

 

E-gcd(n, m)

if( m == 0)

return n

else

 return E-gcd(m, n mod m)

 

★ 왜 n mod m인가?

일단 gcd(n,m) = gcd(n, n mod m)을 증명하면 이 알고리즘이 옳은 알고리즘이라는걸 증명한다.

 

※ 증명 과정

최대공약수를 d, n을 m으로 나눈 몫을 q, 나머지를 r이라 하면

 

n = qm + r

n = C * d (C는 임의의 상수)

qm = C2 * d 므로

n이 d에의해 나누어진다면 qm 그리고 r또한 d에 의해 나누어 떨어진다.

 

따라서 n mod m = r = C3 * d 로 표현 가능하다.

=======================================

유클리드 호제법 증명 (직접 작성)

 직접 증명해보니 뿌듯하구만

한글로 수식작성!!

 

 

Q.  이 알고리즘의 시간복잡도?

 

 

이처럼 문제해결은

 

문제 제시 -> 알고리즘 고안 -> 정확성 분석 -> 성능 분석의 절차를 거친다.