[JAVA] 약수 구하기 & 최소공배수 & 최대공약수 알고리즘, 백준 2609번 최대공약수와 최소공배수 구하기

알고리즘 시험 유형 중 가장 기본 중 기본이 소인수 분해, 약수 구하기가 아닌가 싶다.

당연히 '약수를 구하는 알고리즘을 구현하시오'가 아닌 약수를 이용한 심화된 알고리즘을 풀어야 한다.

 

[약수 구하기]

'약수'란, 어떤 수로 정수가 나누어떨어지는것을 대하여 이르는 말이다.

그리고 1과 자기자신으로밖에 나누어 떨어지지 않는 수를 우리는 소수라고 부른다.

그렇다면 약수를 알고리즘 화 시키는 것은 어떻게 해야할까?

약수의 정의를 조금 다르게 해보자.

어떤 자연수 a, b가 있을 때 a를 b로 나누었을 때 나머지가 0이면 b는 a의 약수라 한다.

이렇게 정의를 알고리즘 화시켜보면 if문과 for문을 어떻게 활용해야할지 감이 잡히게 된다, 

import java.util.*;

public class divisor {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int num = sc.nextInt();
		
		for(int i = 1; i < num; i++) {
			if(num % i == 0) {
				System.out.println(num + " x " + i + " = " + num*i);
			}
		}
	}
}

 

그렇다면 이 약수구하기를 이용하여 최소공배수, 최대공약수를 구해보도록 하자.

 

[최대공약수]

공약수란? 두 개 이상의 자연수의 공통인 약수를 의미한다.

그렇다면 최대 공약수란, 공약수 중에서 가장 큰 수를 의미한다. 또한 최대공약수의 약수는 공약수 이다.

18과 24로 예시를 들어보도록 하겠다.

18의 약수 : 1, 2, 3, 6, 8, 18

24의 약수 : 1, 2, 3, 4, 6, 8, 12, 24

18과 24의 공약수 : 1, 2, 3, 6

18과 24의 최대공약수 : 6

18, 24의 공약수는 6의 약수이다.

그렇다면 이 최대공약수는 어떤 알고리즘으로 되어 있을까?

공약수 구하기는 유클리드 호제법으로 사용할 수 있다.

유클리드 호제법(- 互除法, Euclidean algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.(위키백과 출처)

약수구하기는 위에 코드를 써놨는데 유클리드 호제법을 이용한 최대공약수를 구하는 알고리즘은 어떻게 될까?

* 유클리드 호제법 사용 - While반복문 사용으로 시간복잡도는 O(n)이 된다.

// 유클리드 (a를 b로 나눈 나머지가 0보다 클 때 까지 반복)
static int gcd(int a, int b){ // 최대공약수
	while(b!=0){
		int r = a%b;
		a= b;
		b= r;
	}
	return a;
}

* 재귀함수 사용 - 구현이 간단하며 코드가 간결하다. 시간복잡도는 O(logN)이 된다.

static int GCD(int a, int b){ // 최대공약수
	if (a%b == 0) {
		return b;
	}
	return GCD(b, a % b);
}

 

[최소공배수]

공배수란? 두 개 이상의 자연수의 공통인 배수이다.

최소 공배수는, 공배수 중에서 가장 작은 수를 의미한다. 또한 두 개 이상의 자연수의 공배수는 그들의 최소공배수의 배수이다.

4와 6으로 생각해보자

4의 배수 : 4, 8, 12, 16, 20, 24, 28 ---

6의 배수 : 6, 12, 18, 24, 30, 36 ---

4와 6의 최소 공배수 : 12

4와 6의 공배수는 12의 배수이다.

또한 최소공배수와 최대공약수의 관계가 존재한다.

두 자연수 A, B의 최대공약수가 G이고, 최소 공배수가 L일때,

A = a x G, B = b x G(a, b는 서로소)라 하면 다음이 성립된다.

1. L = a x b x G
2. A x B = L x G

만일 위의 최대공약수 예제였던 18과 24를 예시로 들어보면,

18 = 2^3 * 3 = (2 * 3)*2^2 = gcd(18, 24) * 2^2

24 = 2*3^2 = (2 * 3)*3 = gcd(18, 24) * 3 

lcd(18, 24) = gcd(18, 24) * 2^2 * 3

= gcd(18, 24) * (24 / gcd(18, 24)) * (18 / gcd(18, 24)) 가 될 수 있다.

그럼 이것을 알고리즘화 시키면 어떻게 될까?

static int lcm(int a, int b){ // 최소 공배수
	// 0이 아닌 두 수의 곱 / 두 수의 최대공약수
    return a * b / gcd(a,b);
}

 

이 약수 구하기, gcd와 lcm은 이해하는 것이 가장 중요하겠지만

정말 많이 쓰이므로 이 정도 되는 알고리즘은 꼭 외우도록 하자.

 

자, 이제 백준의 알고리즘 문제로 넘어가보도록 하자.

뭐.. 여기서 더 나아갈것이 있는가

main만 좀 써주고 위의 것들을 복붙하면 끝난다.

import java.util.*;

public class divisor {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		
		System.out.println(gcd(a, b));
		System.out.println(lcm(a, b));
	}
	
	static int gcd(int a, int b){ // 최대공약수
		while(b!=0){
			int r = a%b;
			a= b;
			b= r;
		}
		return a;
	}
	
	static int lcm(int a, int b){ // 최소 공배수
		// 0이 아닌 두 수의 곱 / 두 수의 최대공약수
	    return a * b / gcd(a,b);
	}
	
	static int GCD(int a, int b){ // 최대 공약수
		if (a%b == 0) {
			return b;
		}
		return GCD(b, a % b);
	}

}

 

* 위에서 최대공약수를 구하는 방법 두 가지를 소개하였는데,

반복문을 사용하여 O(N)이 나오는 것과, 재귀함수를 사용하여 O(logN)이 나온다 하였는데,

이 두가지의 성능차이는 아래와 같다.

위에가 재귀함수를 사용하였고 아래가 반복문을 사용하였다.

공간복잡도는 반복문이 더 좋았고

시간복잡도는 재귀함수가 더 좋았다.