수학 문제를 풀다보니 나타난 유클리드 호제법
알고나면 간단한데, 처음에 봤을 땐 무슨 말인가 했다...ㅋㅋㅋ
유클리드 호제법이란?
- Euclidean algorithm
2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘으로,
자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b),
a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
백준 1934번 - 최소공배수
- 문제
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 수를 A와 B의 공배수라고 한다.
이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다.
예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.- 입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다.
둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)- 출력
첫째 줄부터 T개의 줄에 A와 B의
최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.- 풀이
package math;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class LCM { //1934
//유클리드 호제법
/*
최대공약수 GCD = A % B = r 이라 할 때,
재귀함수를 통해 이 r이 0이 되는 순간 B의 값
최소공배수 LCM = 두 수의 곱 / GCD
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while(t-- >0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
System.out.println((a*b) / gcd(a,b));
}
}
public static int gcd(int a, int b){
if(a%b == 0) return b;
else return gcd(b,a%b);
}
}
백준 2981번 - 검문
- 문제
먼저 근처에 보이는 숫자 N개를 종이에 적는다.
그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.
N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.- 입력
첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)
다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다.
이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.
항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.- 출력
첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다.
이때, M은 증가하는 순서이어야 한다.- 내가 푼 풀이 (메모리초과)
package math;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Euclid { //2981 검문
/*
N 수의 개수
수 하나씩 (중복x)
가능한 M 출력 오름차순
*/
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] num = new int[n];
int min = 1000000000;
for (int i = 0; i < n; i++) {
num[i] = Integer.parseInt(br.readLine());
if (min > num[i]) min = num[i];
}
ArrayList<Integer> m = new ArrayList<>();
for (int j = 2; j < min; j++) { //m은 1보다 커야하므로 2부터
HashSet<Integer> remainder = new HashSet<>();
for (int i = 0; i < n; i++) {
int d = num[i] % j;
remainder.add(d);
}
if(remainder.size() ==1) m.add(j); // 어느 수로 나눠도 같은 값이니까
}
Collections.sort(m);
for(int i:m){
System.out.print(i+" ");
}
}
}
유클리드 호제법 이용 문제 풀이 설명
일단 !
배열들을 나눈 값이 같은 M이 공약수가 되므로,
M이 될 수 있는 최대 공약수를 찾고, 그 약수들을 구하면 된다. (1 제외)
뺄셈을 이용하는 이유 !
n이 ASC 정렬된 배열일 때
n1, n2, n3의 나머지를 동일하게 만드는 최대 공약수 M은
n1 % M = n2 % M = n3 % M 이므로 각 항에 뺄셈을 통해
n2 % M - n1 % M = n3 % M - n2 % M
(n2-n1) % M = (n3-n2) % M 이므로 인접한 배열원소를 뺀 후 최대 공약수를 구하면 된다.
- 도움받아 푼 풀이
package math;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Euclid { //2981 검문
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] num = new int[n];
for (int i = 0; i < n; i++) {
num[i] = Integer.parseInt(br.readLine());
}
//배열 정렬
Arrays.sort(num);
int val = num[1]-num[0];
for(int i =2;i<n;i++){ //2부터
val = gcd(val, num[i] - num[i-1]);
}
//최대공약수인 val의 약수 찾기
for (int i =2; i<=val;i++){
if(val%i ==0) System.out.print(i+" ");
}
}
public static int gcd(int a, int b){
/*
while(b != 0){
int d = a%b;
a= b;
b= d;
}
return a;
*/
if(a%b == 0) return b;
else return gcd(b, a%b);
}
}
https://velog.io/@jini_eun/%EB%B0%B1%EC%A4%80-2981%EB%B2%88-%EA%B2%80%EB%AC%B8-Java-Python
𝐃𝐨𝐧'𝐭 𝐛𝐞 𝐚 𝐩𝐫𝐨𝐜𝐫𝐚𝐬𝐭𝐢𝐧𝐚𝐭𝐨𝐫💫