Algorithm/ETC
-
[알고리즘/Algorithm] 최대 공약수, 최소 공배수 공식 유클리드 호제법 알아보기Algorithm/ETC 2021. 8. 9. 15:51
파이썬으로 백준 2609번 최대공약수와 최소공배수 문제(아래 링크)를 풀던 중, 많은 사람들이 최대 공약수와 최소 공배수를 특정한 공식으로 풀고 있던 것을 발견했다. https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 찾아본 결과 그 공식은 '유클리드 호제법' 이라는 공식이였고, 아주 멋진 공식 같아서 좀 더 알아보기로 했다. 네이버 백과사전에 의하면 아래와 같이 정의되어 있다. 솔직히 뭔 소린지 하나도 모르겠다.. 그래서 우선 공식을 외우기로 했다! 때로는.. 처음부터 모든 것을 이해하려고 노력하기 보다는 일단 ..