안녕하세요 이번 시간에는 유클리드 호제법에 대해 포스팅해보겠습니다.
유클리드 호제법이란 두 수의 최대공약수를 구하는 알고리즘입니다. 유클리드 호제법은 다음의 과정으로 동작합니다.
- 큰 수를 작은 수로 나누는 나머지 연산 수행
- 앞 단계에서의 작은 수와 나머지 연산 결과값으로 다시 나머지 연산을 수행하며 1번을 계속 반복
- 나머지가 0이 되는 순간의 작은 수를 최대공약수로 선택
반복되는 구조로 이루어져 있기 때문에 재귀함수로 구현합니다. 파라미터를 (작은 수, 큰 수를 작은 수로 나눈 나머지)로 받은 후 나머지가 0일 경우 작은 수를 리턴, 아닐 경우 재귀함수로 다시 실행하여 결과를 리턴합니다.
백준 1934(최소공배수) 문제를 통해 유클리드 호제법을 구현해보겠습니다. 두 자연수의 최소공배수를 구하는 문제로 최소공배수 = A x B / 최대공약수로 구할 수 있습니다.
import java.util.*;
import java.io.*;
class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while(T-- >0){
StringTokenizer st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
int res = A*B/gcd(A,B);
sb.append(res).append("\n");
}
System.out.println(sb);
}
static int gcd(int a, int b){
if(b == 0) return a;
else return gcd(b, a%b);
}
}백준 1850(최대공약수) 문제의 경우 모든 자리가 1로만 이루어져 있는 자연수의 최대공약수를 구하는 문제입니다. 입력이 각 수의 자리수이기 때문에 각 수의 자리수의 최대공약수를 구한 후 그 크기만큼 1을 출력하면 됩니다.
백준 1033(칵테일) 문제의 경우 총 N-1쌍의 비율이 입력으로 주어질 때 각 재료의 총합이 최소로 하도록 칵테일을 만드는데 필요한 각 재료의 양을 구하는 문제입니다. 각 재료의 총합이 최소가 되려면 모든 비율의 최소공배수를 기준으로 비율을 계산하여 얻은 값을 모든 비율의 최대공약수로 나눈 값을 구해야 합니다. 각 재료를 노드로 하는 그래프를 생성한 후 간선에 p와 q 정보를 저장합니다. 이 때 양방향으로 추가하며 역방향일 경우 p와 q를 반대로 추가합니다. 이어서 각 간선의 p,q의 최소공배수의 모든 곱을 구해 모든 p,q에 대한 최소공배수를 구합니다. 이후 임의의 시작점에서 최소공배수값을 저장한 후 dfs 탐색하여 각 노드의 값을 이전 노드의 값과의 비율을 곱해 저장합니다. 이후 각 노드의 값을 모든 노드의 최대공약수로 나눈 뒤 출력합니다.
