Let IT Begin

* Python을 기준으로 합니다최대공약수 (Greatest Common Divisor, GCD) & 최소공배수 (Least Common Multiple, LCM)- 개념최대공약수 : 두 수의 약수들 중에서 공통되면서 가장 큰 약수최소공배수 : 두 수의 배수들 중에서 공통되면서 가장 작은 배수기본적으로 최대공약수, 최소공배수 모두 완전 탐색으로 찾을 수 있음- 최대공약수의 경우 $O(N)$의 time complexity, 최소공배수는 $O(NM)$의 time complexity가 소모됨이때 유클리드 호제법을 활용하면 최대공약수 계산을 $O(\log n)$으로 해결 가능함유클리드 호제법두 수 $a, b$ ($a>b$)에 대해, $a$를 $b$로 나눈 나머지를 $r$이라 하면, $a$와 $b$의 최대공약수는..