<개인공부>/[Algorithm]

[유클리드 알고리즘] GCD 최대공약수 (반복문, 재귀)

BlockDMask 2017. 7. 14. 08:00
반응형


안녕하세요. BlockDMask 입니다.

유클리드 알고리즘은 사실 알고리즘 카테고리를 새로 만들어서 작성해야하는데,

조만간에 이사하도록 하겠습니다.


1) "유클리드 알고리즘"이란.

  • 유클리드 알고리즘은 주어진 두 수 사이에 존재하는 최대공약수(GCD)를 구하는 알고리즘 입니다. 

  • GCD - greatest common divisor

2) "유클리드 알고리즘" 원리.

  • 임의의 두 자연수 a, b가 주어졌을때. 둘중 큰 값이 a라고 가정해보겠습니다.

  • a를 b로 나눈 나머지를 n 이라고 하면 (a%b = n)

  • n이 0일때, b가 최대 공약수(GCD)입니다.

  • 만약 n이 0이 아니라면, a에 b값을 다시 넣고 n를 b에 대입 한 후 다시 위에 step2부터 반복하면 됩니다.

3) "유클리드 알고리즘" 접근방법.
  • 두가지 접근 방법이 있습니다.
    첫번째) 반복문을 이용한 방법.
    두번째) 재귀를 이용한 방법.
코드에서 main함수 부분은 동일하니, 우선 gcd 함수부분만 따로 비교해서 보겠습니다.

  • 첫번째) 반복문을 이용해서 최대공약수(GCD)를 구하는 코드를 보겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int gcd(int a, int b){
    int tmp, n;
 
//a에 큰 값을 위치시키기 위한 조건문입니다.
    if(a<b){
        tmp = a;
        a = b;
        b = tmp;
    }
    
//유클리드 알고리즘 부분입니다.
//b가 0이 될때까지(a%b), 반복문을 돌게되고, b가 0인 순간의 a를 GCD로 판단하고 리턴합니다.
    while(b!=0){
        n = a%b;
        a = b;
        b = n;
    }
    return a;
}
cs

**함수 내부의 변수를 하나만 선언해도 되지만 위에서 n을 a 나누기 b의 나머지라 설명했으므로 변수를 두개 선언했습니다.


  • 두번째) 재귀함수(recursive)를 이용해서 최대공약수(GCD)를 구하는 코드를 보겠습니다.

1
2
3
4
5
6
7
8
9
10
int gcd(int a, int b){
    
    if(b == 0){
        return a;
    }else{
        return gcd(b, a%b);
    }
}
//재귀함수 부분이 훨씬 간단하고, swap 함수를 하는 부분도 필요 없음을 확인 할 수 있습니다.
//재귀함수는 코드를 보기에는 클린하지만 메모리를 많이 잡아 먹는 경우도 있습니다.(피보나치같은 경우)
cs


**두가지 방법의 장단점을 잘 숙지하는 것이 좋은 방법인 듯 싶습니다.

  • 제가 정의한 main 함수 부분입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<stdio.h>
#include<stdlib.h>
int main(int argc, char * argv[]){
    
    int a = atoi(argv[1]);
    int b = atoi(argv[2]);
    int result;
    printf("a : %d, b : %d\n", a, b);
 
    result = gcd(a, b);
 
    printf("gcd : %d\n", result);
    return 0;
}
cs

  • 출력 결과 입니다.
    func는 반복문(while)을 기반으로 구현한 "유클리드 알고리즘" 입니다.
    recur은 재귀(recursive)를 기반으로 구현한 "유클리드 알고리즘" 입니다.


반응형