GCD, LCM과 유클리드 알고리즘
약수를 빠르고 정확하게 계산합니다
GCD, LCM과 유클리드 알고리즘은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
약수가 중요한 이유
많은 대회 문제는 두 수가 공유하는 인수에 달려 있습니다. 여기서 가장 유용한 도구는 최대공약수인 GCD입니다. 🔢
GCD의 의미
두 정수의 GCD는 나머지 없이 두 수를 모두 나누는 가장 큰 수입니다. 12와 18의 경우 6이 두 수를 모두 정확히 나누므로 GCD는 6입니다.
느린 방법
작은 수부터 시작해 모든 수를 아래로 하나씩 확인하면서 두 수를 모두 나누는 수를 찾을 수 있습니다. 작동하기는 하지만 큰 입력에서는 너무 느립니다.
유클리드 알고리즘의 통찰
유클리드 알고리즘은 빠른 방법입니다. 핵심 아이디어는 a와 b의 GCD가 b와 a를 b로 나눈 나머지의 GCD와 같다는 것입니다.
점화식
나머지가 0이 될 때까지 교환과 나머지 연산을 반복합니다. 마지막으로 남는 0이 아닌 값이 바로 답, 즉 GCD입니다.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = a직접 코드 작성하기
짧은 반복문에서 b가 0이 될 때까지 쌍을 계속 바꿉니다. 약 로그 단계만 실행되므로 매우 큰 수에도 놀라울 만큼 빠릅니다.
def gcd(a, b):
while b:
a, b = b, a % b
return a표준 라이브러리 사용하기
직접 구현할 필요는 거의 없습니다. Python에는 정확하고 빠르며 인수가 0인 경우도 처리해 주는 math.gcd가 내장되어 있습니다.
from math import gcd
print(gcd(12, 18))GCD에서 LCM으로
LCM은 최소공배수로, 두 값이 모두 나누어지는 가장 작은 수입니다. 방금 계산한 GCD와 직접 연결됩니다.
LCM 공식
두 수를 곱한 다음 GCD로 나눕니다. 매우 큰 곱에서 오버플로가 발생하지 않도록 항상 먼저 나누십시오.
def lcm(a, b):
return a // gcd(a, b) * b전체 목록의 GCD
여러 수에 걸쳐 GCD를 누적하려면 수를 두 개씩 차례로 처리하십시오. Python의 누적 함수는 목록에 대해 왼쪽에서 오른쪽으로 math.gcd를 적용합니다.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)0인 경우 처리하기
정의에 따라 gcd(a, 0)은 a이고 gcd(0, 0)은 0입니다. 이 경계 경우를 알고 있으면 빈 입력에서 반복문이 잘못 작동하는 것을 막을 수 있습니다.
빠른 확인
유클리드 알고리즘의 핵심 단계를 확인할 시간입니다.
복습
이제 유클리드 알고리즘으로 GCD를 로그 단계 안에 계산하고, 그 결과로 LCM을 구하며, 목록 전체에 두 연산을 누적할 수 있습니다. ✅
자주 묻는 질문
“GCD, LCM과 유클리드 알고리즘” 강의는 무료인가요?
네 — “GCD, LCM과 유클리드 알고리즘” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“GCD, LCM과 유클리드 알고리즘”에서 뭘 배우나요?
약수를 빠르고 정확하게 계산합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“GCD, LCM과 유클리드 알고리즘” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- GCD, LCM과 유클리드 알고리즘
- sqrt(n)까지의 소수 판정
- 에라토스테네스의 체
- 소인수 분해와 약수