[Algorithm] 약수·최대공약수·최소공배수

목표

---

알고리즘 문제를 풀면서 약수·최대공약수·최소공배수를 구하는 문제를 만났는데 기본적으로 구현을 할 수는 있지만, 관련 공식을 쓰지 않아 매우 비효율적으로 답을 찾고 있다는 것을 깨달았다. 약수·최대공약수·최소공배수를 구하는 경우는 생각보다 자주 보이기때문에 이 기회에 정리해두려고 한다. 해당 문제를 만나면 공식을 쓸 수 있도록 이해하고 코드로 정리해보자.

 

 

약수(Divisor) 구하기

---

12의 약수를 구한다고 할때, 처음 약수를 구할때는 아래와 같이 1부터 12까지 반복문을 돌려서 나머지가 0이되는 숫자를 찾는 식으로 접근했다. 하지만, 이렇게 접근하면 O(n)의 시간복잡도를 가지게 되는데 n이 커지고 문제가 복잡해진다면 분명 매우 큰 시간을 잡아먹을 것이다.

List<Integer> divisor = new ArrayList<>();

int num = 12;
for(int i=1; i<=num; i++) {
	if(num % i == 0) divisor.add(i);
}

 

 

Math 라이브러리의 sqrt() 함수를 사용하면 위 문제를 어느정도 개선할 수 있다. sqrt() 함수는 인자로 들어온 정수의 제곱근을 구해주는데 sqrt(12)를 호출한다면 12의 제곱근인 3.xxx의 값을 반환한다. 이러한 sqrt() 함수를 이용해 기존에 O(n)의 시간복잡도를 가지는 알고리즘에서 O(sqrt(n))의 시간복잡도로 약수를 구할 수 있다. 아래 개선된 코드를 보자. 코드를 i가 1부터 3까지만 반복문을 돌아도 12의 약수를 모두 구할 수 있음을 알 수 있다. i가 12의 약수라면 그 반대인 12/i도 무조건 12의 약수가 되는 원리를 이용한다.

List<Integer> divisor = new ArrayList<>();

int num = 12;
double sqrt = Math.sqrt(num);
for(int i=1; i<=sqrt; i++) {
    if(i == sqrt) {
    	divisor.add(i);
        break;
    }
    if(num % i == 0) {
        divisor.add(i);
        divisor.add(num/i);
    }
}

 

 

최대공약수 GCD(Greatest Common Divisor) 구하기

---

최대공약수는 유클리드 호제법을 이용하여 쉽게 구할 수 있다. 78696과 19332의 최대공약수를 유클리드 호제법을 이용해 구하면 32의 최대공약수가 나오는데 그 과정은 아래와 같다.

78696 = 19332*4 + 1368
19332 = 1368*14 + 180
1368 = 180*7 + 108
180 = 108*1 + 72
108 = 72*1 + 36
72 = 36*2 +0

 

a가 b보다 클때, 최대공약수를 구하는 알고리즘은 정말 위 수식을 코드로 옮기기만 하면 된다.

public int gcd(int a, int b) {
    while(b != 0) {
        int tmp = a;
        a = b;
        b = (tmp % a);
    }

    return a;
}

 

 

최소공배수 LCM(Least Common Multiple) 구하기

---

최소공배수는 정수 a와 b의 곱을 a와 b의 최대공약수로 나누면 구할 수 있다. 위에서 최대공약수를 구하는 함수를 만들었기 때문에 최대공약수 함수를 이용해서 최소공배수를 구하는 함수는 손쉽게 구현할 수 있다.

public int lcm(int a, int b) {
	return (a*b)/gcd(a, b);
}

 

 

 

 

[ 참고자료 ]

[Java/알고리즘] 유클리드 호제법(Euclidean Algorithm) : 최대공약수, 최소공배수