최대공약수를 구하는 3가지 방법

https://mk28.tistory.com/193 참고

 

1) [1, min(a, b)] 범위에서 두 수 모두의 약수가 되는 값 중 최댓값을 구하는 방법

• 시간복잡도 O(min(a,b)), 시간초과가 발생하기 쉬움

 

2) 역순 탐색 - [1, min(a, b)]부터 1까지 역순으로 탐색하여 가장 처음 발견된 공약수가 결국 최대 공약수가 됨

• 1번 방법을 역순으로 진행하고, 공약수가 발견되면 break하는 방법으로 구현
• 1번보다는 빠르겠지만 최악의 경우 모든 수를 검사함
• 1번과 동일한 시간 복잡도

 

3) 유클리드 호제법

f(a, b) = gcd(a, b)라 하자.

이 때 a mod b = 0 이라면, f(a, b) = b임이 자명.

이 때 a mod b이 0이 아닌 경우, f(a, b) = f(b, a mod b)가 성립한다. 

이를 유클리드 호제법이라고 함

• 반복문이나 재귀 함수를 이용하여 구현
• 정수 a와 b에 대하여 근사적으로 O(log2(min(a,b)))의 시간복잡도를 가짐

 

---

이제까지 1번 방법으로 gcd를 구했는데, 백준 9613번을 풀며 내 방식이 시간 초과가 나기 쉬운 방법임을 깨달았다 ...!

유클리드 호제법을 익혀서 유클리드 호제법으로 gcd 문제를 풀자 !!