lcm 검색 결과

해당 글 2건
python math의 lcm 함수에 대해 간단하게 알아봅시다.

python math의 lcm은 여러 정수의 최소 공배수를 구하기 위한 함수입니다. 1번째 예제입니다. 2와 3의 최소공배수를 구하라고 했습니다. 결과는 6이 나올 겁니다. 왜냐하면 2와 3의 공배수 중 최소인 것은 6이기 때문입니다. 여기까지는 별로 어렵지 않습니다. 당연한 것이니까요. 이제 0과 5의 최소 공배수를 구하려고 합니다. 어떻게 나올까요? 문서를 찾아보면, 하나라도 0이 있는 경우에 무조건 0이 나온다고 되어 있습니다. 따라서, 이 경우에는 0이 나오게 됩니다. 정말 그리 나오네요. 만약에 음수가 있으면 어떻게 될까요? -4와 6의 최소공배수를 구하려고 합니다. 이 경우, -4의 multiple과 6의 multiple이면서 가장 값이 작은 positive integer를 돌려줍니다. mul..
레퍼런스/예제 2023. 4. 9. 23:57
최대공약수 최소공배수 알고리즘 : 짧은 코드 이해해 봅시다.

오늘은 간단하게, 최대 공약수와 최소 공배수를 구하는 알고리즘을 알아보도록 하겠습니다. 먼저 a와 b의 최대 공약수란, a와 b를 동시에 나누어 떨어지게 하는 최댓값을 의미해요. 예를 들어서 a가 6이고 b가 3이라면 3이 gcd가 됩니다. 그렇다면 가장 간단한 알고리즘을 생각해 볼 수 있습니다. a와 b의 최솟값을 r이라고 해 봅시다. r부터 1까지 계속 a와 b를 나누어 보면서, 만약에 두 수를 동시에 나누는 수가 있다면 break를 걸어버리는 겁니다. 사실, 이러한 방법은 꽤 효과적일 수 있습니다. 그런데 a = 20억, b = 10억 7 정도가 된다고 하면, 수행 시간이 상당히 길어질 겁니다. 왜냐하면 b는 소수이기 때문입니다. b를 나누는 수는 1과 10억 7밖에 없는데, 20억을 나누는 수는 ..
자료알고/알고리즘 2019. 8. 7. 17:50