728x90
1. 유클리드 호제법(Euclidean Algorithm)
유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘입니다.
두 수의 최대공약수란, 두 수를 모두 나누어 떨어지는 가장 큰 수를 말합니다.
유클리드 호제법은 다음과 같은 과정으로 이루어집니다.
- 두 수 중에서 큰 수를 A, 작은 수를 B라고 합니다.
- A를 B로 나눈 나머지를 R이라고 합니다. 즉, A를 B로 나눈 나머지를 구합니다.
- R이 0이 되면, B가 두 수의 최대공약수입니다.
- R이 0이 아니면, 이제 B를 R로 대체합니다.
- 다시 R을 B로 나누고 나머지를 구합니다.
- 위 과정을 나머지가 0이 될 때까지 반복합니다.
- 나머지가 0이 되면, 그 때 B가 최대공약수(GCD)가 됩니다.
💡 유클리드 호제법/알고리즘(Euclidean Algorithm) 이란?
- 두 수의 “최대공약수(GCD)”를 찾기 위한 알고리즘을 의미합니다.
- 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될때까지 작동하는 방법을 의미합니다.
- 그때 작은 수가 최대공약수입니다.
2. 두 수의 약수와 배수 구현
2. 1 약수 구하기
for 문을 통해 1부터 n까지 반복하며 n을 i로 나누어 나머지가 0인 경우, 즉 약수일 때마다 i를 출력
int n = 약수를 구할 수;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
System.out.println(i);
}
}
2. 1 배수 구하기
int n = 배수를 구할 수;
for (int i = 1; i <= 10; i++) {
System.out.println(n * i);
}
3. 두 수의 최대 공약수와 최소 공배수 구현
3.1 최대 공약수(GCD) 구현
위의 유클리드 호제법 이용하여서 “최대공약수(GCD)”를 구하는 방식을 구현
이 방식은 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될 때까지 작동하여 최대공약수를 구하는 방식
1. 재귀 함수로 구현
- B가 0이라면 A가 최대공약수가 되며, 그렇지 않으면 B와 A % B(A를 B로 나눈 나머지)의 최대공약수를 구함
- 이를 재귀적으로 반복하여 최대공약수를 구함
// 재귀 방식
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
2. 반복문으로 구현
- 먼저, B가 0이 될 때까지, A % B(A를 B로 나눈 나머지)를 B에 대입하고, A와 B의 값을 교환
- 이를 반복하여 최대공약수를 구함
// 반복문 방식
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
3.2 최소 공배수(LCM) 구현
최대공약수의 함수를 기반으로 “최소공배수”를 구합니다.
해당 방식은 함수 내부에서 두 수 A와 B의 최대 공약수를 이용하여 최소 공배수를 계산
최소 공배수는 두 수의 곱에 최대 공약수를 나눈 값과 같습니다.
예를 들어, 12와 18의 최대공약수는 6 -> 12와 18의 최소공배수는 12 x 18 / 6 = 36
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
728x90
'공log > [JAVA]' 카테고리의 다른 글
[JAVA] 자바 #5 - 정규식 (1) | 2023.10.23 |
---|---|
[JAVA] 자바 #4 - 투 포인터 (0) | 2023.09.25 |
[JAVA] 자바 #3 - 제네릭 (1) | 2023.09.25 |
[JAVA] 자바 #2 - 진법 변환하기 (0) | 2023.09.04 |