목록GCD (1)

승코딩당당당

유클리드 호제법 (euclidean-algorithm)

코딩 테스트에서 수학 알고리즘 문제를 풀다 보면 자주 등장하는 개념이 바로 최대공약수(GCD)이다. 최대공약수를 구하는 가장 기본적인 방법은 두 수를 소인수 분해한 뒤, 공통된 소수들의 곱을 구하는 것이다.하지만 이 방법은 구현이 번거롭고, 큰 수에 대해서는 비효율적이다. 이를 훨씬 간단하고 빠르게 구할 수 있는 방법이 바로 유클리드 호제법(Euclidean Algorithm) 이다.이번 글에서는 유클리드 호제법의 원리와 동작 과정, 그리고 왜 이 방법이 효율적인지 정리해보려고 한다. ✍️ 유클리드 호제법이란?유클리드 호제법은 두 수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 알고리즘이다.이 알고리즘의 핵심 아이디어는 다음과 같다.두 수 A와 B에 대해 A를 B로 나..
개발/알고리즘 2026. 3. 2. 17:32
이전 Prev 1 Next 다음