[유클리드 호제법 알고리즘] 최대공약수, 최소공배수 구하기
유클리드 호제법 1. 최대공약수 최대공약수를 구하는 가장 쉬운 알고리즘, 유클리드 호제법 두 수 A와 B가 주어졌다고 생각해보자. (A>B) A와 B의 최대 공약수는 n이라고 하자. 그러면 A=n*?, B=n*?? 이런 구조일 것이다. 결국 A-B, B-(A-B), (A-B)-(B-(A-B)) ,,,,,,,, 이런 식으로 계속 빼다보면 언젠가 최소 단위인 n이 나올 것이다. 이 그림을 보면 이해가 될 것이다. A에서 B를 빼고, 다시 B에서 그 A-B를 빼고 이런 과정을 반복하다 보면 언젠가 n이 나오고 맨 마지막엔 0이 나올 것이다. 둘 다 n이 남았으니 말이다. 여기서 아이디어를 추가해보자. 계속 빼는 것도 좋지만, A와 B의 차이가 크면 너무 무의미한 계산의 반복이다. 결국 A%B, A를 B로 나눈..
2022. 1. 14.
