유클리드 알고리즘.md

유클리드 알고리즘

문제

양의 정수 $a$와 $b$의 최대공약수 $g = gcd(a, b)$를 구하시오. 여기서 $g$는 나머지 없이 $a$와 $b$ 모두 나누는 가장 큰 수로 정의한다.

발상

유클리드 알고리즘은 큰 수에서 작은 수를 빼면 두 수의 최대공약수가 변하지 않는다는 단순한 관찰을 기반한다:

$a > b$인 상황에서 $g$는 $a$와 $b$의 최대공약수라고 하자. 그렇다면 $g$는 $a$와 $b$를 나눌 수 있다. 따라서 $g$는 $a - b$도 나눌 수 있다. (분배법칙)

$g'$를 $b$와 $a - b$의 최대공약수라 하자.

$g' = g$ 귀류법:

$g' < g$ 또는 $g' > g$이라고 가정하자.

$g' < g$일 때, $g'$는 최대 공약수가 될 수 없다. $g$도 $a - b$와 $b$의 공약수이기 때문이다.

$g' > g$일 때, $g'$는 $b$와 $a - b$의 약수이다 - 즉, $g'n = b$와 $g'm = a - b$로 표현할 수 있는 정수 $n, m$이 존재한다. 따라서 $g'm = a - g'n \iff g'm + g'n = a \iff g'(m + n) = a$이다. 이는 $g'$도 $a$의 약수이며, $g$가 $a$와 $b$의 최대공약수라는 초기 가정과 $g' > g$는 모순이다.

구현

실제 실행에서 속도를 높이기 위해 반복해서 뺄셈하는 대신 나머지 연산이 사용된다: $b$는 $a >= b$만큼 $a$에서 여러 번 반복해서 뺄 수 있다. 이러한 뺄셈 후에는 $b$로 나눌 때 $a$의 나머지만 남게 된다.

간단한 Lua 구현은 다음과 같다:

function gcd(a, b)
	while b ~= 0 do
		a, b = b, a % b
	end
	return a
end

%가 나머지 연산자임을 유의하자; 각 단계에서 새로운 a에 b를 할당하고, 새로운 b에는 a를 b로 나눈 나머지 연산한 값을 할당한다.

분석

공간 복잡도

공간 복잡도는 약간 일정하다: (일정한 크기로 가정된) $a$와 $b$라는 두 개의 숫자만 저장한다.

시간 복잡도

while문의 각 반복은 일정한 시간에 실행되며 최소한 $b$를 절반으로 줄인다. 따라서 $O(log_2(n))$는 런타임의 상한값이다.

연습

$a = 42$와 $b = 12$의 최대공약수를 구하라:

1. $42 \mod 12 = 6$
2. $12 \mod 6 = 0$

결과는 $gcd(42, 12) = 6$.

유클리드 알고리즘을 사용하여 $a = 633$와 $b = 142$의 최대공약수를 구하라:

1. $633 \mod 142 = 65$
2. $142 \mod 65 = 12$
3. $65 \mod 12 = 5$
4. $12 \mod 5 = 2$
5. $5 \mod 2 = 1$
6. $2 \mod 1 = 0$

결과는 $gcd(633, 142) = 1$: $a$와 $b$는 서로소이다.

활용

• 분수 단축하기
• 최소공배수 구하기
• 두 수가 서로소인지 효율적으로 확인하기 (예: RSA 암호화 시스템에 필요)

참고자료

• 위키피디아 "유클리드 호제법" 항목