알고리즘 - 유클리드 호제법

알고리즘 - 유클리드 호제법

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질을 이용한다.

이를 사용해 최대공배수를 구할 수 있는데, 두 수의 곱을 유클리드 호제법으로 구한 최대공약수로 나누면 그것이 최대공배수이다.

 

jina-developer.tistory.com/77

프로그래머스 Level 2 - N개의 최소공배수

부정 방정식 : 해가 무수히 많은 방정식, 미지항의 개수보다 방정식의 개수가 작을 경우도 부정방정식에 포함된다.

 

디오판토스 방정식 : 해가 정수인 경우의 부정 방정식 (3x + 2y = 5)

 

베주 항등식 : 정수 x, y의 최대공약수를 gcd(x, y)로 나타낼 때, 확장 유클리드 호제법을 이용하여 ax + by = gcd(x, y)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다. (a, b 중 한 개는 보통 음수가 된다.) 이 식을 베주의 항등식이라고 한다.

 

[ 확장 유클리드 호제법 ]

ax + by = c 형태의 방정식이 주어질 때 이 방정식을 만족 시키는 정수 x, y를 각각 s, t라고 정의하고, 우변의 상수값에 유클리드 호제법 (r" - qr' = r)을 사용하여 반복적으로 구하는 값들을 r이라고 하면 아래 방정식을 만족시키는 정수 해 s와 t가 반드시 존재한다. 처음에는 1, 0, 0, 1순서로 먼저 계산

ax + by = a, ax + by = b

여기서부터 아래 단계를 반복적으로 적용하면서 r값을 줄여나가면 최종적으로 우변의 값을 만들 수 있는 r값을 찾을 수 있고, 이 때 s와 t값을 통해 해를 구할 수 있다.

- r = r" - qr'식을 통해 q와 r을 계산한다.

- s = s" - qs', t = t" - qt'식을 통해 s와 t를 계산한다.

 

213x + 720 = 3 -> 71x + 240y = 1

s	t	r	q
1	0	71
0	1	240
1	0	71	0
-3	1	27	3
7	-2	17	2
-10	3	10	1
17	-5	7	1
-27	8	3	1
71	-21	1	2

x = 71, y = -21

 

만약 우변이 a와 b의 최대공약수의 배수가 아닌 경우 방정식을 만족하는 정수해가 존재하지 않는다.