목록최대공약수 (1)
꿈 많은 사람의 이야기
파이썬 알고리즘 공부 - 최대공약수, 최소공배수 구하기
최대공약수, 최소공배수 구하는 것은 심심하면 나오는 과제입니다 처음 이 문제를 접했을 때는 최소공배수, 최대공약수가 뭐였는지도 기억이 안났던게 기억이 나네요 크흠.. 그래서 이번 글은 파이썬으로 최대공약수, 최소공배수를 구현해봅니다 먼저 최대공약수입니다 최대공약수는 소인수분해를 이용해서 구하는 방법도 있습니다. 뭐 예를 들어 60과 48이 있다고 가정하면 60 = 2^2 * 3 * 4 48 = 2^4 * 3 이니까 공통된 수 중 지수가 작은 것을 골라내면 2^2 * 3 = 12가 최대공약수가 됩니다. 근데 이 방법 말고 유클리드 호제법을 사용하면 더 쉽게 구현할 수 있습니다 유클리드 호제법은 위의 설명에도 나와있지만, 192와 72가 있으면 큰 숫자를 작은 숫자로 나누어 나머지를 구합니다. 192 % 7..
알고리즘&자료구조
2019. 5. 7. 07:35