유클리드 호제법 (euclidean-algorithm)
유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시한다.
유클리드 호제법의 핵심 이론
유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 한다. MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문이다.
| 연산 | 기능 | 예제 |
| MOD | 두 값을 나눈 나머지를 구하는 연산 | 10 MOD 4 = 2 // 10 % 4 = 2 |
MOD 연산을 이해하면 다음과 같은 3단계로 유클리드 호제법을 구현할 수 있다.
- 큰 수를 작은 수로 나누는 MOD 연산을 수행한다.
- 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다.
- 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다.
유클리드 호제법의 원리 이해하기
예시를 보며 이해해 보자. 다음은 270과 192의 최대 공약수를 유클리드 호제법으로 찾아보는 그림이다.
[백준 1934번] 최소공배수
https://www.acmicpc.net/problem/1934
최소 공배수는 A와 B가 주어졌을 때 'A * B / 최대 공약수' 를 계산해 구할 수 있다. 결국 이 문제는 유클리드 호제법을 이용해 최대 공약수를 구한 후 두 수의 곱에서 최대 공약수를 나눠 주는 것으로 해결할 수 있다.
책에서는 재귀 함수로 풀었는데 난 반복문으로 풀었다. 재귀가 확실히 더 깔끔하고 보기 좋은 것 같은데 쉽게 잘 생각나지 않는다. (최소 공배수 = A x B / 최대 공약수) 를 기억하자.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int i = 0; i < T; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int result = a * b / gcd(a, b);
System.out.println(result);
}
}
public static int gcd(int a, int b) {
if(b == 0)
return a;
else
return gcd(b, a % b);
}
}
[원본]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int big = Math.max(A, B);
int small = Math.min(A, B);
if(big % small == 0) {
bw.write(big + "\n");
continue;
}
int gcd = 0;
while (big % small != 0) {
gcd = big % small;
big = small;
small = gcd;
}
int answer = gcd * (A / gcd) * (B / gcd);
bw.write(answer + "\n");
}
bw.flush();
bw.close();
}
}
[백준 1850번] 최대공약수
https://www.acmicpc.net/problem/1850
예제의 규칙
- 수의 길이를 나타내는 두 수의 최대 공약수는 A와 B의 최대 공약수의 길이를 나타낸다.
- 즉, 3, 6의 최대 공약수 3은 A(111)와 B(111111)의 최대 공약수(111)의 길이로 나타난다.
처음엔 두 자릿수의 차이만큼 1을 붙여야 하나, 자릿수가 짝수이고 홀수이냐에 따라 뭐가 있나, 등등 생각해 봤지만 그냥 넌씨눈 문제다. 예제로 들어온 입력의 최대 공약수를 구하면 그것이 정답의 길이가 된다. 추가로 출력 횟수가 많기 때문에 그냥 String에 냅다 계속 붙이면 시간 초과가 발생하므로 BufferedWriter를 사용해야 한다.
[정답]
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
long A = sc.nextLong();
long B = sc.nextLong();
long result = gcd(A, B);
while (result > 0) {
bw.write("1");
result--;
}
bw.flush();
bw.close();
}
public static long gcd(long A, long B) {
if(B == 0) return A;
else return gcd(B, A % B);
}
}
[백준 1033번] 칵테일
https://www.acmicpc.net/problem/1033
문제에서는 N - 1개의 비율로 N개의 재료와 관련된 전체 비율을 알아낼 수 있다고 했다. 이것을 그래프 관점으로 생각하면 사이클이 없는 트리 구조로 이해할 수 있다. 이 내용을 바탕으로 임의의 노드에서 DFS를 진행하면서 정답을 찾으면 된다. DFS 과정에서 유클리드 호제법을 사용해 비율들의 최소 공배수와 최대 공약수를 구하고, 재료의 최소 질량을 구하는 데 사용해 문제를 해결해 보겠다.
1. 인접 리스트를 이용해 각 재료의 비율 자료를 그래프로 구현한다.
2. 데이터를 저장할 때마다 비율과 관련된 수들의 최소 공배수를 업데이트한다.
A, B의 최소 공배수는 A * B / 최대 공약수
=> 1, 3, 5, 7의 최소 공배수는 105
3. 임의의 시작점에 최소 공배수 값을 저장한다.
4. 임의의 시작점에서 DFS로 탐색을 수행하면서 각 노드의 값을 이전 노드의 값과의 비율 계산을 통해 계산하고 저장한다.
- 0을 임의의 점으로 선정
=> 0에서 DFS로 탐색을 수행하면 0 -> 4 -> 1 -> 2 -> 3 순으로 탐색
- 4 => 0번 노드값 * 1 / 1 = 105
- 1 => 4번 노드값 * 1 / 3 = 35
- 2 => 4번 노드값 * 1 / 5 = 21
- 3 => 4번 노드값 * 1 / 7 = 15
5. 각 노드의 값을 모든 노드의 최대 공약수로 나눈 뒤 출력한다.
105, 35, 21, 15, 105의 최대 공약수는 1
=> 각 배열의 값을 1로 나눠 출력 => 105, 35, 21, 15, 105
[정답]
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<cNode>[] A;
static long lcm;
static boolean visited[];
static long D[];
public static void main(String[] args) throws IOException{
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = sc.nextInt();
A = new ArrayList[N];
visited = new boolean[N];
D = new long[N];
lcm = 1;
for (int i = 0; i < N; i++) {
A[i] = new ArrayList<cNode>();
}
for (int i = 0; i < N - 1; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int p = sc.nextInt();
int q = sc.nextInt();
A[a].add(new cNode(b, p, q));
A[b].add(new cNode(a, q, p));
lcm *= (p * q / gcd(p, q));
}
D[0] = lcm;
DFS(0);
long mgcd = D[0];
for (int i = 1; i < N; i++) {
mgcd = gcd(mgcd, D[i]);
}
for (int i = 0; i < N; i++) {
System.out.println(D[i] / mgcd + " ");
}
}
public static long gcd(long a, long b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
public static void DFS(int Node) {
visited[Node] = true;
for (cNode i : A[Node]) {
int next = i.getB();
if (!visited[next]) {
D[next] = D[Node] * i.getQ() / i.getP(); // 주어진 비율로 다음 노드값 갱신
DFS(next);
}
}
}
static class cNode{
int b;
int p;
int q;
public cNode(int b, int p, int q) {
super();
this.b = b;
this.p = p;
this.q = q;
}
public int getB() {
return b;
}
public int getP() {
return p;
}
public int getQ() {
return q;
}
}
}
모든 수의 최소 공배수 구함 -> 나온 비율대로 최소 공배수 곱해줌 -> 모든 수의 최대 공약수로 다 나눠줌
[참고 자료]
- Do it! 알고리즘 코딩 테스트 자바편
'알고리즘 > Do it! 알고리즘 코딩 테스트' 카테고리의 다른 글
| 그래프의 표현 (1) | 2024.06.04 |
|---|---|
| 정수론 - 확장 유클리드 호제법 (0) | 2024.06.01 |
| 정수론 - 오일러 피 (0) | 2024.05.30 |
| 정수론 - 소수 구하기 (1) | 2024.05.29 |
| 그리디 (0) | 2024.05.28 |
