유클리드 호제법을 이용한 최대공약수, 최소공배수

Created on November 23, 2023

2023   ·   PS   ·   Algorithm

💡 최대공약수, 최소공배수 함수 미리보기

먼저 알고리즘을 알고있지만 복붙이나 복습을 위해 찾아온 사람들을 위해 코드를 먼저 보여주겠다.

처음 보는거라면 꼭 아래로 내려가 이해해보도록 하자.

파이썬 (Python)

  • 최대공약수 (Greatest Common Divisor, GCD)
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
  • 최소공배수 (Lowest Common Multiple, LCM)
def lcm(a, b):
    return a * b // gcd(a, b)

자바 (Java)

  • 최대공약수 (Greatest Common Divisor, GCD)
public static int gcd(int a, int b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
}
  • 최소공배수 (Lowest Common Multiple, LCM)
public static int lcm(int a, int b) {
    int gcd = gcd(a, b);
    return (a * b) / gcd;
}

💡 유클리드 호제법 (Euclidean Algorithm) ?

2개의 자연수의 최대공약수(GCD) 를 구하는 알고리즘이다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘을 나타낸다.

a>b인 자연수 a, b에 대해서 a를 b로 나눈 나머지를 c이라 하면,

a와 b의 최대공약수는 b와 c의 최대공약수와 같다.

계속해서 b를 c로 나눈 나머지 d를 구하고,

다시 c을 d로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

💡 알고리즘 이해

아래의 738 과 2034의 최소공약수를 구해보면서 이해해보자.

큰 수에서 작은 수를 나누고 나누어 떨어지지 않는다면 나머지를 구한다.

기존의 작은수와 새로 생긴 나머지를 나누고 나누어 떨어지지 않는다면 나머지를 구하는 작업을 반복한다.

결국 나누어 떨어지면 그때 나누었던 작은 값이 최대공약수이다.

a b c d e  
2034 738 2034%738 = 558      
  738 558 738%558 = 180    
    558 180 558%180 = 18  
      180 18 180%18 = 0

💡 코드 이해

재귀함수를 사용하여 쉽게 만들 수 있다. 자바 코드로 이해해보자.

최대공약수 (Greatest Common Divisor)

public static int gcd(int a, int b) {
    if (b == 0) { // 나머지가 0 : 나누어떨어진다면 마지막
      return a;  // 나머지였던 a를 리턴하여 재귀함수를 종료한다.
    }
    return gcd(b, a % b); // 나누어떨어지지 않는다면 재귀함수를 계속 진행한다.
}

최소공배수 (Least Common Multiple)

최대공약수 함수를 사용해야한다.

최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같다.

public static int lcm(int a, int b) {
    int gcd = gcd(a, b);
    return (a * b) / gcd; 
}         // 최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같다.

💡 코드 테스트 - 백준 13241번: 최소공배수

백준 최소공배수 문제

1. 유클리드 호제법을 사용한 풀이

import java.util.Scanner;

public class Main {
	
  // 이 문제에서는 입력값이 매우 크므로 long을 사용해야 하므로 int를 long으로 바꿔준다.
  
	public static long gcd(long a, long b) { 
	    if (b == 0) {
	      return a;
	    }
	    return gcd(b, a % b);
	}
	
	public static long lcm(long a, long b) {
	    long gcd = gcd(a, b);
	    return (a * b) / gcd;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		sc.close();
		
		System.out.println(lcm(a, b));
	}
}

2. 일반 for문을 사용한 풀이 (알고리즘 X)

import java.util.Scanner;

public class Main { 

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		long b = sc.nextLong();
		long gcd = 1;
		for(int j=2; j<=100000000;) { //2부터 1억까지 공약수의 소인수가 가능한 것을 하나하나 확인
			if(a % j == 0 && b % j == 0) { //동시에 나눠지면 (공약수의 소인수)
				a /= j;	//a도 공약수의 소인수로 나누고
				b /= j;	//b도 공약수의 소인수로 나누고
				gcd *= j; // j 는 최대공약수의 소인수이므로 곱하면서 저장
			}
			else {
				j++; //안나눠질때만 다음으로 넘어감. 2^4 * 3^2 이런 식의 소인수분해가 가능하기 때문
			}
		}
		long	lcm = a * b * gcd; //여기서 a b는 서로소이므로 셋을 곱하면 최소공배수이다.
		System.out.println(gcd);
		System.out.println(lcm);
		sc.close();
	}

}

결과

둘 다 맞았지만 시간에서 엄청난 차이가 보인다.

아래가 일반 for문을 사용한 풀이이고, 2부터 1억까지 공약수의 소인수가 가능한 것을 하나하나 확인했기 때문에 시간이 오래걸렸다.

위는 유클리드 호제법을 사용해 6배 빠른 결과를 얻은 걸 볼 수 있다.

💡 시간복잡도

  • 기존의 for문을 사용하여 무차별적으로 대입한다면 시간복잡도는 O(N)이다.
  • 유클리드 호제법을 사용할 경우 (a, b) 에서 (b, c) 로 축소될 때, 순서쌍의 곱이 최소 2배 이상 줄어든다.
  • 따라서 한번마다 최소 2배씩 감소하므로 시간복잡도는 O(logN) 이다.

💡 결론

  • 최대공약수나 최소공배수를 이용할때 꼭 잊지말고 사용하자.