algorithmmath

알고리즘 | 유클리드 알고리즘(최대공약수)

유클리드 알고리즘 (최대공약수)

최대 공약수
A = aG; (280 = 2810)
B = bG; (30 = 310)

A-B = aG - bG = (a-b) * G
(a-b) 와 b는 역시 서로소 이므로 A-B와 B의 최대 공약수는 역시 G

[뺄셈 이용] -> 성능 최악

  1. 임의의 두 정수 u와 v를 입력 받는다
  2. v가 u보다 크다면 v와 u의 값을 교환한다
  3. u에다 u-v의 값을 저장한다
  4. u가 0인가?
    • 0이 아니면 2로 돌아간다
    • 0이면 v가 최대 공약수이다 
1
2
3
4
5
6
7
8
9
10
11
int get_gcd(int u, int v)
{
    int t;
    while(u){
        if(u<v){
            t = u; u = v; v = t;
        }
        u =    u - v;
    }
    return v;
}

10 == 250%30
나머지 연산을 이용하면 여러번의 뺄셈 대신에 한번의 %연산으로 대체할 수 있다
큰수 / 작은수 -> 나머지 이용

[나누기 -> 나머지 이용]

  1. 임이의 두 정수 u와 v를 입력 받는다

  2. v가 0인가?

    • 0이면 v가 최대 공약수이다 끝

    • 0이 아니면 2.1 u에 u%v를 대입한다

      2.2 u와 v의 값을 교환한다

1
2
3
4
5
6
7
8
9
10
int get_modulus(int u, int v)
{
    int t;
    while(v){
        t = u%v;
        u = v;
        v = t;
    }
    return u;
}

[재귀 방법]
속도는 나머지를 이용하는 방법보다 느리지만 소스코드의 간결 장점

1
2
3
4
5
int gcd_recursion(int u, int v)
{
    if(v == 0)    return u;
    else return gcd_recursion(v, u%v);
}
Share