[알고리즘] 최대 공약수와 최소 공배수

최대 공약수 GCD

• 최대 공약수를 두 수 혹은 여러 수가 가지는 약수들에서 서로 동일하게 가지는 약수들 중 가장 큰 수를 말한다.

1. 기본적인 최대 공약수 알고리즘

   1. 두 수 n과 m중 더 작은 숫자부터 1까지 인덱스 i로 탐색한다.
   2. 탐색을 진행하면서 n과 m을 i로 나누었을때 나머지가 0이다. (나누어 떨어진다.) 조건을 만족한다면 해당 i를 배열에 저장한다.
   3. 탐색을 마치고 배열에 저장된 수들 중 가장 큰 수를 가져온다.
   • 이 방식의 단점
     • 최대 공약수를 구하려는 숫자가 엄청나게 크다면 탐색해야 하는 범위가 너무 넓어져 효율성이 떨어 질 수 있다.
     • O(N)의 시간 복잡도를 가진다.
   • 코드

       // 기본적인 방법
       public int gcd1(int a, int b) {
               int size = Math.min(a,b);
               for(int i = size; i > 0; i--) {
                   if(a % i == 0 && b % i == 0) return i;
               }
           return 1;
         }
   
       // 유클리드 호제법 - 반복문을 이용한 방법
       public int gcd2(int a, int b) {
               while(a%b != 0) {
                       int tmp = a % b;
                       a = b;
                       b = tmp;
               }
               return b;
       }
       
       // 유클리드 호제법 - 재귀를 이용한 방법
       public int gcd3(int a, int b) {
               if (a % b == 0) return b;
               return gcd(b, a%b);
   	}

2. 유클리드 호제법을 적용한 최대 공약수 알고리즘

   1. 두 수 n,m중 더 큰 수를 a에 할당, 더 작은 수를 b에 할당 한다.
   2. 큰 수 a를 작은 수 b로 나눈 나머지를 구한다.
      • 두 수 중 작은 수로 큰 수가 나누어 떨어지면 두 수의 최대 공약수는 작은 수 b가 된다.
   3. 나머지가 발생 했다면 큰 수 a의 자리에 이전 연산에서 작은 수 역할을 했던 b를 할당하고 작은 수 b의 자리에는 이전 연산에서 구한 나머지 c를 할당한다.
   4. 할당 후 b ~ c 과정을 반복해 b과정에서 c과정으로 넘어가지지 않는 순간 (두 수가 나누어 떨어진 순간) 작은 수 b는 두 수의 최대 공약수가 된다.
   • 이 방식의 단점
     • 한 번에 두 개의 숫자만을 가지고 최대 공약수를 구할 수 있다. 3개의 숫자 이상의 최대 공약 수를 구하려면 먼저 두 개의 숫자의 최대 공약수를 구하고 그 최대 공약수와 세번째 숫자의 최대 공약수를 구하는 순서를 반복해야 한다. 동시에 여러개의 숫자의 최대 공약수를 구해야 할 때는 첫 번째 방식이 더 유리할 수 있다.
       
     • O(logN)의 시간 복잡도를 가진다.

• 유클리드 호제법을 표현한 그림

최소 공배수 LCM

• 최소 공배수는 두 수 혹은 여러 수의 배수들에서 서로 겹치는 배수들 중 가장 작은 배수를 말한다.
• 최소 공배수를 구하는 알고리즘

  1. 위의 최대 공약수를 구하는 알고리즘을 상황에 따라 선택에 적용한다.

  2. 두 수의 곱을 최대 공약수로 나눈다.

     유클리드 호제법을 적용한 최대 공약수 구하는 알고리즘과 같이 여러 수의 최소 공배수를 구해야하는 경우 앞의 두 수의 최소 공배수를 구해서 그 다음수와 최소공배수를 구하는 방법식으로 진행 하면된다.

     이 또한 O(logN)의 시간 복잡도를 가진다.

• 코드

  pubilc int gcd(int a, int b) {
  		if (a % b == 0) return b;
  		return gcd(b, a%b);
  }
  
  pubilc int lcm(int a, int b) {
  		return (a * b) / gcd(b, a%b);
  		// 자바는 int형끼리 나누면 자동으로 몫 나눗셈 결과가 나온다.
  }