728x90
1) 무엇일까?
유클리드 알고리즘은 두 수의 최대공약수(gcd)를 계산하는 알고리즘 중 하나이다.
유클리드 호제법이라고도 하는데 같은 의미이다.
확장된 유클리드 알고리즘은
특정 a와 b에 대해서 as + bt = gcd(a,b)인 s와 t를 구하는 알고리즘이다.
2) 선후관계
확장된 유클리드 알고리즘은
유클리드 알고리즘을 사용하기 때문에, 유클리드 알고리즘을 먼저 알고 있어야 이해할 수 있다.
3) 유클리드 알고리즘
유클리드 알고리즘은 최대공약수의 두가지 기초 성질을 이용한 알고리즘이다.
a(나눠지는 수) = q(몫) * b(나누는 수) + r(나머지) 이라 할 때 (필수조건 : a >= b)
1. gcd(a, 0) = a 이다.
2. gcd(a, b) = gcd (b, r)
4) 유클리드 알고리즘 - 로직
2번 성질을 이용해 b와 r을 또 몫과 나머지로 쪼개고 그것을 또 쪼개고를 반복해
gcd( b' , 0)로 나누는 수가 0이 될 때까지 반복하면
1번 성질에 의해 b'이 a와 b의 최대 공약수가 된다.
5) 유클리드 알고리즘 - 증명
우선 1번
'a와 0의 최대공약수는 a이다.'
0에는 무슨 수를 나눠도 0으로 나눠떨어지기 때문에, 모든 수가 0의 약수가 되고
당연히 a와의 최대공약수라고 한다면 a가 될 것이다.
이 부분은 쉽게 넘어갈 수 있을거라고 생각한다.
2번
'a와 b의 공약수는 a를 b로 나눈 나머지와 b의 공약수이다.'
이는 이해하기 어려울 수 있어서 증명이 필요하다.
처음부터 다시 얘기하면
a >=b 가 기본 가정이고, 그렇다면 a와 b의 관계를 a = q * b + r와 같이 나타낼 수 있다.
쉽게 설명하면 a가 b보다 크기 때문에 a를 b로 나누면 몫 q와 나머지 r이 생긴다는 뜻이다.
여기서
gcd(a , b) = g라 하고 gcd(b , r) = e라 하자.
r = a - q * b 이고
a와 b의 최대공약수가 g
r = k1 * g - q * (k2 *g)
728x90
