유클리드 알고리즘

1. 최대공약수(GCD, Greatest Common Divisor)

: 주어진 두 정수의 약수 중에서 가장 큰 공통약수

ex) 280과 30의 GCD는 10이다.

- 소인수분해를 통해 GCD를 구할 수 있다.

- 관련 법칙

GCD(u, v) = GCD(u-v, v), if u > v

280, 30일 때 250, 30의 최대공약수와도 같다.

GCD(u, v) = GCD(v, u)

280, 30이나 30, 280이나 최대공약수는 같다.

GCD(u, 0) = u

280, 0

2. 유클리드 알고리즘

: 임의의 두 정수 u, v에 대해

1) v가 u보다 크면 v와 u의 값을 바꾼다.

2) u = u - v

3) u가 0이면 v가 최대공약수, 0이 아니면 1)로 돌아감

ex) GCD(280, 30)

GCD(250, 30)   - 1)

GCD(220, 30)

GCD(190, 30)

GCD(160, 30)

GCD(130, 30)

GCD(100, 30)

GCD(70, 30)

GCD(40, 30)

GCD(10, 30)

GCD(30, 10)    - 2)

GCD(20, 10)

GCD(10, 10)

GCD(0, 10)     - 3)

=> 10

- 코드

int get_gcd(int u, int v) {

int t; // u와 v를 교환하기 위한 임시 변수

while (u) { // 3), 0이면 3), 0이 아니면 1) 진행

if (u < v) { // 2)

t = u;

u = v;

v = t;

}

u = u-v;

}

return v;

}

- 특징

: 위의 알고리즘은 뺄셈에 기반하기 때문에 u, v 값 차이가 클 때 많은 뺄셈을 요구하게 된다.

=> 뺄셈은 나눗셈의 나머지를 구하는 것

GCD(u, v) = GCD(u%v, v) = GCD(v, u%v), u%v < v

3) 개선된 유클리드 알고리즘

: 임의의 두 정수 u, v에 대해

1) v != 0

1.1) u = u%v

1.2) u와 v를 교환

1.3) 1)로 돌아감

2) v == 0

GCD = u

ex) GCD(30, 280)

GCD(280, 30)

GCD(10, 30)

GCD(30, 10)

GCD(0, 10)

GCD(10, 0)

=> 10

- 코드

int gcd_upgrade(int u, int v) {

int t; // u와 v를 교환하기 위한 임시 변수

while (v) { // v > 0

t = u%v;

u = v;

v = t;

}

return u;

}

- 재귀로 표현

int gcd_recursion(int u, int v) {

if (v == 0)

return u;

else

return gcd_recursion(v, u%v);

}

- 관련 문제

백준 1934번

참고 사이트