[알고리즘] 프로그래머스(Level1) - 최대공약수와 최소공배수(Java) / 최대공약수와 최소공배수 알고리즘(유클리드 호제법)

https://programmers.co.kr/learn/courses/30/lessons/12940

코딩테스트 연습 - 최대공약수와 최소공배수

 

 

최대공약수

 

최대공약수를 구하는 방법 중 가장 쉬운 공식에는 유클리드 호제법이 있다. 유클리드 호제법이 무엇인지 알기에 앞서 왜 쓰는 지에 대해서 알아보자.

2개의 자연수를 받아 최대공약수를 구하기 위해 1부터 두 자연 수 중 작은 자연수까지 모두 나누어 보면 최대공약수를 구할 수 있다. 하지만 이 방법의 시간복잡도는 O(N)이다. 하지만 유클리드 호제법을 이용한 알고리즘은 시간복잡도를 O(N)에서 O(logN)으로 줄일 수 있기 때문에 사용한다. N이 작은 숫자이면 별 차이가 없지만, N이 1억이라고 생각하면 굉장히 큰 차이가 나기 때문에 유클리드 호제법을 사용하는 것이 좋은 방법이라는 것을 알 수 있다.

 

유클리드 호제법

 

2개의 자연수 a, b (a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대 공약수와 같다. 

 

 

위의 말을 수식으로 나타내면 

 

GCD(A, B) = GCD(B, A%B)
if A%B = 0 -> GCD = B
else GCD(B, A%B)

 

수식으로 보면 이해가 잘 안 될 수도 있으니 예시를 보면 확인해보자.

	GCD(A, B)	A	B	A % B
1	GCD(80, 32)	80	32	16
2	GCD(32, 16)	32	16	0

 

1번째에서 A%B가 0이 아니므로 같은 과정을 한 번 더 반복한다.

2번째에서 A%B가 0이므로 최대공약수는 16이다.

 

 

재귀함수를 이용하지 않은 최대공약수 구하기 솔루션

 

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int a = n;
        int b = m;
        while(b > 0) {
            int r = b;
            b = a%b;
            a = r;
        }

        answer[0] = a;

        return answer;
    }
}

 

 

 

재귀함수를 이용한 최대공약수 구하기

 

수식으로 정리된 유클리드 호제법을 보면 재귀함수를 이용해 풀 수도 있겠다는 생각을 하게 되어 재귀함수로 코드를 작성해 보았다.

 

public int gcd(int n, int m) {
	if(m==0) return n;
	return gcd(m, n%m);
}

 

 

최소공배수

 

최소공배수의 성질을 이용하면 쉽게 풀 수 있다.

 

두 수 a와 b의 곱을 a와 b의 최대공약수로 나눈 것과 같다.

 

이 성질을 이용하면 간단히 몇 줄로 최소공배수를 구하는 코드를 짤 수 있다.

 

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
		
		answer[0] = this.gcd(n, m);
		answer[1] = this.lcm(n, m);
		
		return answer;
	}		
	//최대공약수 구하는 메소드
	public int gcd(int n, int m) {
		if(m==0) return n;
		return gcd(m, n%m);
	}
	//최소공배수 구하는 메소드
	public int lcm(int n, int m) {
		return n*m / this.gcd(n, m);
	}
}