GCD, LCM과 유클리드 알고리즘

많은 대회 문제는 두 수가 공유하는 인수에 달려 있습니다. 여기서 가장 유용한 도구는 최대공약수인 GCD입니다. 🔢

두 정수의 GCD는 나머지 없이 두 수를 모두 나누는 가장 큰 수입니다. 12와 18의 경우 6이 두 수를 모두 정확히 나누므로 GCD는 6입니다.

작은 수부터 시작해 모든 수를 아래로 하나씩 확인하면서 두 수를 모두 나누는 수를 찾을 수 있습니다. 작동하기는 하지만 큰 입력에서는 너무 느립니다.

유클리드 알고리즘은 빠른 방법입니다. 핵심 아이디어는 a와 b의 GCD가 b와 a를 b로 나눈 나머지의 GCD와 같다는 것입니다.

나머지가 0이 될 때까지 교환과 나머지 연산을 반복합니다. 마지막으로 남는 0이 아닌 값이 바로 답, 즉 GCD입니다.

짧은 반복문에서 b가 0이 될 때까지 쌍을 계속 바꿉니다. 약 로그 단계만 실행되므로 매우 큰 수에도 놀라울 만큼 빠릅니다.

직접 구현할 필요는 거의 없습니다. Python에는 정확하고 빠르며 인수가 0인 경우도 처리해 주는 math.gcd가 내장되어 있습니다.

LCM은 최소공배수로, 두 값이 모두 나누어지는 가장 작은 수입니다. 방금 계산한 GCD와 직접 연결됩니다.

두 수를 곱한 다음 GCD로 나눕니다. 매우 큰 곱에서 오버플로가 발생하지 않도록 항상 먼저 나누십시오.

여러 수에 걸쳐 GCD를 누적하려면 수를 두 개씩 차례로 처리하십시오. Python의 누적 함수는 목록에 대해 왼쪽에서 오른쪽으로 math.gcd를 적용합니다.

정의에 따라 gcd(a, 0)은 a이고 gcd(0, 0)은 0입니다. 이 경계 경우를 알고 있으면 빈 입력에서 반복문이 잘못 작동하는 것을 막을 수 있습니다.

유클리드 알고리즘의 핵심 단계를 확인할 시간입니다.

이제 유클리드 알고리즘으로 GCD를 로그 단계 안에 계산하고, 그 결과로 LCM을 구하며, 목록 전체에 두 연산을 누적할 수 있습니다. ✅