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

안녕하세요. 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)를 구하는 코드를 보겠습니다.
  

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;
}

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

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

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

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

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

#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;
}

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