[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
- 문제
- 알고리즘 [접근 방법]
아마 알고리즘을 많이 접해본 사람들은 GCD를 사용하여 풀었거나 한 번쯤은 들어봤을 것이다. 일단 간단한 알고리즘 코드로 보자면 이렇다.
[GCD]
// 반복문 방식
int gcd(int a, int b) {
while(b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
// 재귀 방식
int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a % b);
}
근데 GCD에서 정작 제대로 이해하고 있지 못하거나 '그냥 그러니까' 라고 넘어가는 사람들도 있어 이 번 기회에 한 번 정리하고 가셨으면 한다. 그리 어렵지 않은 개념이니 차근차근 이해해보도록 하자.
최대공약수 GCD
GCD가 대체 무슨 뜻일까? Greatest Common Divisor. 즉 가장 큰 공통된 약수라는 의미다. 최대공약수는 어릴 때부터 배워왔으니 구하는 것 자체는 어렵지 않지만 보통 이렇게 배웠을 것이다.
"A와 B 두 수가 주어지면 A의 약수들을 모두 구하고, B의 약수들을 모두 구한 뒤 공통 된 약수들만 찾아내어 약수들의 곱으로 다시 나타내준다."
물론 이렇게 풀어도 된다. 단 단점이 있다. 어떤 수가 약수가 매우 많을경우 그 것을 인수분해하는데 시간을 많이 필요로 하게되며 또한 두 수를 비교한 뒤 다시 곱해주는 것도 너무 많은 시간을 소비하게 된다. 그래서 최대공약수 또는 최소공배수를 사용하기 위해 보통은 앞서 보여준 알고리즘 방식을 사용하게 된다. 이름하여 '유클리드 호제법'이다.
유클리드 호제법 (Euclidean algorithm)
(잠깐 잡지식으로 하나 추가하자면 영어식 이름으로 유클리드지만, 고전어(?) 방식으로는 에우클레이데스라고 읽는다. 마치 우리는 '현대(Hyundai)'라고 읽지만 외국 사람들은 '현다이'라고 읽듯이..)
유클리드 호제법은 생각보다 매우 오래된 알고리즘이다. 기원전 300년경이라고 하는데.. 그만큼 매우 유명한 알고리즘 중 하나라는 것이다. 근데 왜 호제법이라고 부를까?
호제법이 사실 올바른 말인지는 모르겠으나.. 한자로 표현하면 互除法(호제법)이다. 互(서로 호), 除(나눌 제, 뺄 제) 즉 서로 나눈다는 의미로 호제라고 표현했다. (참고로 중국에서는 辗转相除法라고 표현하는 것 같다.)
여간 왜 최대공약수 알고리즘이 위와 같은지를 알아야하지 않겠는가.
유클리드 호제법의 정리는 다음과 같다.
두 수 ,
이 때 r은 (0 ≤ r < b) 이고, a ≥ b 이다.
이 때 a 와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다.
즉, 아래와 같다는 의미다.
GCD(a, b) = GCD(b, r)
음... 무슨 말일까 싶을 것이다. 예로 하나 들어보자. 두 수 581, 322 가 있다고 가정해보자.
GCD(581, 322)일 때 r(나머지) = 259이다. 즉, GCD(581, 322) = GCD(322, 259)이다.그럼 다시 GCD(322, 259)를 보면 r=63이다. 그러면 GCD(322, 259) = GCD(259, 63)이다.또 다시 GCD(259, 63)을 보면 r=7이다. 즉, GCD(259, 63) = GCD(63, 7)이다.
다시 GCD(63, 7)을 보면 r=0 이다. 그러면 GCD(63, 7) = GCD(7, 0)이다.
결과적으로 나머지가 없다는 것은 공통된 약수로 나누어 떨어진다는 의미이므로 7이 최대공약수가 된다. 쉽게 쓰면 이렇다.
GCD(581, 322) = GCD(322, 259) = GCD(259, 63) = GCD(63, 7) = GCD(7, 0) = 7
신기하지 않은가?? 왜 위의 정리가 만족하는지 증명을 해보도록 하자. 조금의 수학적 지식이 있다면 쉽게 이해할 수 있을 것이다.
A, B
그리고 GCD(A, B) = d 라고 한다면 A와 B는 각각 다음과 같이 나타낼 수 있다.
A = ad, B = bd (자연스럽게 a, b는 서로소가 된다.)
A = Bq + r를 이항하면 다음과 같은 식으로 표현 할 수 있다.
이 때 B 와 A 는 각각 ad 와 bd 로 표현 할 수 있기 때문에 결과적으로 다음과 같은 식을 만족한다.
r = = ad - bdq = (a - bq)d
위 식을 잘 생각해보면 이렇게 생각 할 수 있다. B = bd 와 r = (a - bq)d 로 B 와 r 은 d 를 공통된 약수로 갖는다.즉, d는 B와 r의 공약수라는 것이다. 하지만 아직 공약수일 뿐이지 d가 최대 공약수인지는 증명이 안되었다.
최대공약수인지를 확인하는 방법은 b 와 (a - bq) 가 서로소임을 증명하면 된다. 이 것은 귀류법으로 쉽게 증명이 가능하다. 한마디로 앞서 전제한 b 와 (a - bq) 가 서로소가 아니라고 하고 여기서 모순을 도출하면 된다.
b 와 (a - bq) 가 서로소가 아니라는 의미는 '두 수는 공약수를 갖고 있다는 의미'다.이 때 b 와 (bq - a) 의 공약수를 p 라고 두면 다음과 같이 표현이 가능하다.
b = mp, (a - bq) = np
이때 a - bq = np 에 b = mp 를 대입하면 아래와 같이 만들 수 있다.
(a - bq) = np → (a - mpq) = np
이항을 하면 다음과 같이 만들 수 있다.
mpq + np = a
⇒ (mq + n)p = a
그러면 a = (mq + n)p 와 b = np 에서 a와 b는 p를 공약수로 갖는다. 어? 맨 처음 A = ad, B = bd 에서 a 와 b 는 서로소인데? 즉, 모순이된다는 의미다. 결과적으로 b와 (a - bq)도 서로소라는 것이고 자연스럽게 d도 최대공약수라는 것을 알 수 있다.
또한 d 는 B 와 r 의 공약수라고 했으니, d 는 최대공약수이므로 GCD(A, B) = GCD(B, r) 또한 만족한다.
이렇게 증명이 완료되었다.
근데 이러한 의문이 들 수 있다. "왜 최대공약수만 증명하고 최소공배수 구하는 방법은 왜 안알려줘?"이에 대한 대답은 최소공배수는 진짜 너무 쉽다는 것.
우리가 앞서 GCD(최대공약수)를 증명했다.
생각해보자 A=ad, B= bd 에서 a 와 b 는 서로소이고, d 는 최대공약수라고 했다. 쉽게 말하자면 두 수의 '소인수분해'를 한 결과의 공통된 부분이 최대공약수, 즉 d 라는 것이다.
그러면 두 수의 최소 공배수는 자연스럽게 a×b×d 이지 않겠는가?
만약 위 문제처럼 A와 B로 주어진다면 A = ad, B= bd이었으므로 a×b×d를 만족하려면 A × B 만 하면 adbd로 d가 한 번 더 들어가 있으니 A × B ÷ d 를 해주면 a×b×d 를 만족하면서 최소공배수가 된다.
한 마디로 최대공약수를 구해준 뒤 입력받은 두 수의 곱에서 최대공약수를 나눠주면 끝난다.
이를 알고리즘으로 구성하자면 다음과 같을 것이다.
// 최대공약수 반복문 방식
int gcd(int a, int b) {
while(b != 0) {
int r = a % b; // 나머지를 구해준다.
// GCD(a, b) = GCD(b, r)이므로 변환한다.
a = b;
b = r;
}
return a;
}
// 최대공약수 재귀 방식
int gcd(int a, int b) {
if(b == 0) return a;
// GCD(a, b) = GCD(b, r)이므로 (r = a % b)
return gcd(b, a % b);
}
// 최소공배수 : Least Common mulitple
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
- 4가지 방법을 사용하여 풀이한다.
알고리즘은 위에서 설명한 유클리드 호제법을 이용하여 풀 것이다. 대신 최대공약수를 구하는 과정에서 재귀방식과 반복문 방식을 비교하면서 또한 입력방식도 바꿔서 받아보려 한다.
1 . Scanner + 재귀
2 . Scanner + 반복문
3. BufferedReader + 재귀
4. BufferedReader + 반복문
- 풀이
- 방법 1 : [Scanner + 재귀]
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
int d = gcd(a, b); // 최대공약수
System.out.println(d);
System.out.println(a * b / d);
}
// 최대공약수 재귀 방식
public static int gcd(int a, int b) {
if (b == 0)
return a;
// GCD(a, b) = GCD(b, r)이므로 (r = a % b)
return gcd(b, a % b);
}
}
가장 기본적인 방법이다. 증명은 앞서 다 했으니 그리 어렵지 않았을 것이다.
- 방법 2 : [Scanner + 반복문]
Scanner 입력 방식에 알고리즘은 재귀방식이 아닌 반복문을 사용하여 풀이하는 방법이다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
int d = gcd(a, b); // 최대공약수
System.out.println(d);
System.out.println(a * b / d);
}
// 최대공약수 반복문 방식
public static int gcd(int a, int b) {
while (b != 0) {
int r = a % b; // 나머지를 구해준다.
// GCD(a, b) = GCD(b, r)이므로 변환한다.
a = b;
b = r;
}
return a;
}
}
- 방법 3 : [BufferedReader + 재귀]
입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 A와 B를 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int d = gcd(a, b); // 최대공약수
System.out.println(d);
System.out.println(a * b / d);
}
// 최대공약수 재귀 방식
public static int gcd(int a, int b) {
if (b == 0)
return a;
// GCD(a, b) = GCD(b, r)이므로 (r = a % b)
return gcd(b, a % b);
}
}
매우 쉽죠?
- 방법 4 : [BufferedReader + 반복문]
재귀 대신 반복문을 이용하여 풀이하는 법이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int d = gcd(a, b);
System.out.println(d);
System.out.println(a * b / d);
}
// 최대공약수 반복문 방식
public static int gcd(int a, int b) {
while (b != 0) {
int r = a % b; // 나머지를 구해준다.
// GCD(a, b) = GCD(b, r)이므로 변환한다.
a = b;
b = r;
}
return a;
}
}
크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.
- 성능
채점 번호 : 23363380 - 방법 4 : BufferedReader + 반복문
채점 번호 : 23363368 - 방법 3 : BufferedReader + 재귀
채점 번호 : 23363359 - 방법 2 : Scanner + 반복문
채점 번호 : 23363354 - 방법 1 : Scanner + 재귀
언제나 변함없이 입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다. 근데 알고리즘의 성능차이가 있는 것인지는.. 조금 차이가 있어보이긴 한데, 어찌되었건 평균적으로 재귀보다는 반복문이 더 빠르긴 하다.
- 정리
오늘은 유클리드 호제법에 대해서 좀 집중적으로 다뤄보았다. 사실 알고리즘이야 워낙 쉽기도 하고 손처럼 익혀져있어서 그냥 쓰는 경우가 많은데 이번 기회로 한 번 제대로 왜 이러한 코드인지 한 번쯤은 되돌아 보았으면 했다.
사실 증명까지는 못외우더라도 최소한 '왜 이러한 알고리즘이 있는 것이지?'라는 질문에 대한 답 정도는 해야지 정말 필요한 곳에 적절하게 쓰고 변형할 수 있기도 한 것 또한 사실이다. 이 정도야 워낙 쉬운 편이니까 문제가 크지 않은데 후에 좀 더 어려운 알고리즘으로 들어가면 정확한 이해 없이는 응용하여 쓰기 힘든 알고리즘들이 많으니 이렇게 증명을 뜯어보는 습관을 들이면 좋지 않을까?
혹여 이 글에서 어렵거나 익숙하지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.
'JAVA - 백준 [BAEK JOON] > 정수론 및 조합론' 카테고리의 다른 글
| [백준] 11050번 : 이항 계수 1 - JAVA [자바] (17) | 2020.10.27 |
|---|---|
| [백준] 3036번 : 링 - JAVA [자바] (0) | 2020.10.23 |
| [백준] 2981번 : 검문 - JAVA [자바] (10) | 2020.10.22 |
| [백준] 1037번 : 약수 - JAVA [자바] (6) | 2020.10.15 |
| [백준] 5086번 : 배수와 약수 - JAVA [자바] (0) | 2020.10.14 |