알고리즘: 유클리드 호제법(최대공약수, gcd)

유클리드 호제법

유클리드 호제법은 두 수 A,B의 최대공약수를 구하는 알고리즘이다. 

 

방법

• A=0이면 GCD(0,B)=B이므로 GCD(A,B)=B이고 멈춤.
• B=0이면 GCD(A,0)=A이므로 GCD(A,B)=A이고 멈. 
• A를 A = B⋅Q + R의 형식으로 씀. (Q는 A를 B로 나눈 몫.)
• GCD(A,B) = GCD(B,A-B)이므로 유클리드 호제법을 이용하여 GCD(B,A-B)를 찾음.

 

예시:

270과 192의 최대공약수 - GCD(270,192)

1. GCD(270,192) - 270과 192의 최대공약수 찾기
   • A=270, B=192
   • A ≠ 0
   • B ≠ 0
   270 = 192 * 1 +78
2. GCD(270,192)=GCD(192,78) - 이기 때문에 192와 78의 최대공약수 찾기
   • A=192, B=78
   • A ≠0
   • B ≠0
   192 = 78 * 2 + 36
3. GCD(192,78)=GCD(78,36) - 이기 때문에 78과 36의 최대공약수 찾기
   • A=78, B=36
   • A ≠0
   • B ≠0
   78 = 36 * 2 + 6
4. GCD(78,36)=GCD(36,6) - 이기 때문에 36과 6의 최대공약수 찾기
   • A=36, B=6
   • A ≠0
   • B ≠0 36 = 6 * 6 + 0
5. GCD(36,6)=GCD(6,0) - 이기 때문에 6과 0의 최대공약수 찾기
   • A=6, B=0
   • A ≠0
   • B =0, GCD(6,0)=6
6. GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6

---

GCD의 구현:

unsigned int gcd(unsigned int a, unsigned int b)
{
 if (a < b) return gcd(b, a);
 if (b == 0) return a;
 else return gcd(b, a - b);
}

기존 방식. (-를 사용)

unsigned int gcd(unsigned int a, unsigned int b)
{
 if (a < b) return gcd(b, a);
 if (b == 0) return a;
 else return gcd(b, a % b);
}

개선된 방식. (%를 사용)

---

백준 1850: 최대공약수

https://www.acmicpc.net/problem/1850