알고리즘 문제를 풀다보면 낮은 난이도에서 자주 나오는 최대공약수, 최소공배수 문제를 마주치게 될 것이다.
야! 그거 모르는 사람이 어딨어? 초딩때 다 배우잖아?
물론 다 배우는 것은 맞지만, 나같이 알린이들은 코딩으로 구현 하려고하면 생각보다 바로 떠오르지 않을 것이다.
그렇게 최대공약수, 최소공배수를 구하는 법을 찾아보다 유클리드 호제법 을 알게되었다.
유클리드 호제법 ? 그게 뭔데?
단순히 말하면 최대공약수를 구하는 공식이다.
그냥 단순히 말하자면 그렇다는 것이다. 다른 곳에서 깊게 알고싶다면 이 블로그방문을 추천한다.
결론만 말하자면 자연수 a, b 는 하나의 공식으로 묶인다
a와 b의 최대공약수를 (a,b) 라고하면, (a,b)의 최대공약수는 (b,r).
여기서 r = a % b;
결론 : GCD(a,b) = GCD(b,r)
이러한 공식이 성립되는데, 이해하기 쉽게 예를 들어보겠다.
자연수 a = 196, b = 81 이라고 하자.
a와 b의 최대공약수를 구하는 문제를 마주했을 때 상황을 가정하면,
b가 0이 될 때까지 두 수의 나눈 나머지와 b를 나누면 된다.
(196, 84) = (84, 28) = (28, 0)
최대공약수를 표현하는 괄호안의 오른쪽 숫자(b)가 0이 됐을 때 왼쪽 숫자가 두 수의 최대공약수이다.
즉 196과 84의 최대공약수는 28인 셈이다. 이해가 됐으려나
그러면 최소공배수는?
앞서 언급한 블로그에 가면 자세한 증명이 있으니 확인할 사람들은 가보도록.
결론만 말하자면 두 자연수 A와 B는 A = ad, B = bd 로 구성하고 있고, d는 최대공약수이고 a와 b는 서로소이다.
그렇다면 서로소의 최소공배수를 구하는 법은 다 알듯이 두 수를 곱하는 것이다.(약수가 없으니까)
그렇다면 AxB가 최소공배수가 되는 것 일텐데, A = ad, B = bd이니 최소공배수는 adbd가 될 것이고,
여기서 d는 두번 곱해졌으니 한번 나눠주는 것이다. A × B ÷ d 를 해주면 a×b×d 를 만족하면서 최소공배수가 된다.
정리 : GCD(a,b) = GCD(b,r)을 통해 최대공약수를 구하고, 두 자연수의 곱에 최대공약수를 나누면 최소공배수이다.
ps) 이해에 정말 큰 도움을 준 Stranger-Lab님 감사합니다..
