안녕하세요! 이번 글에서는 자바를 활용하여 코딩 테스트에서 자주 출제되는 문제 중 하나인 “최대 공약수 구하기”에 대해 알아보겠습니다. 알고리즘 문제를 해결하는 과정에서 필요한 기초 지식부터, 문제 해결을 위한 단계별 접근법과 자바 코드 구현까지 상세히 설명하겠습니다.
1. 문제 설명
주어진 두 개의 정수 a와 b에 대해, 이 두 수의 최대 공약수(Greatest Common Divisor, GCD)를 구하는 문제입니다. 최대 공약수란 두 수의 공통된 약수 중 가장 큰 약수를 의미합니다. 예를 들어, a = 12와 b = 15일 경우, 두 수의 약수는 다음과 같으며:
- 12의 약수: 1, 2, 3, 4, 6, 12
- 15의 약수: 1, 3, 5, 15
따라서 12와 15의 최대 공약수는 3입니다.
2. 문제 접근법
최대 공약수를 구하는 방법에는 여러 가지가 있지만, 그 중에서 **유클리드 호제법**(Euclidean algorithm)이 매우 효율적이고 널리 사용됩니다. 유클리드 호제법의 기본 아이디어는 다음과 같습니다:
- 두 정수 a와 b가 있을 때, a를 b로 나눈 나머지를 r이라 하자.
- 그러면, GCD(a, b) = GCD(b, r)입니다. 즉, a와 b의 최대 공약수는 b와 a를 b로 나눈 나머지의 최대 공약수와 같습니다.
- 이 과정을 r이 0이 될 때까지 반복합니다. 이때, b가 GCD(a, b)입니다.
이 방법은 매우 효율적이며, 시간 복잡도가 O(log(min(a, b)))로 비교적 짧은 시간 안에 결과를 도출할 수 있습니다.
3. 자바 코드 구현
이제 위의 알고리즘을 바탕으로 자바 코드를 구현해 보겠습니다. 아래는 최대 공약수를 구하는 자바 코드입니다:
public class GCD {
// 유클리드 호제법을 이용한 최대 공약수 계산 메서드
public static int gcd(int a, int b) {
// b가 0일 때 a가 최대 공약수
if (b == 0) {
return a;
}
// 재귀 호출로 나머지를 이용하여 최대 공약수 계산
return gcd(b, a % b);
}
public static void main(String[] args) {
int a = 12; // 첫 번째 정수
int b = 15; // 두 번째 정수
int result = gcd(a, b); // 최대 공약수 계산
System.out.println("최대 공약수: " + result); // 결과 출력
}
}
4. 코드 설명
위의 코드에서 gcd 메서드는 두 개의 정수 a와 b를 매개변수로 받아 최대 공약수를 계산합니다. 메서드 내부에서 b가 0인지 체크하고, 0이라면 a를 반환합니다. 그 외의 경우, 재귀적으로 gcd 메서드를 호출하여 a와 b의 나머지를 인자로 전달합니다. 이 과정을 반복하여 최종적으로 최대 공약수가 도출됩니다.
5. 다양한 입력 테스트
코드가 정상적으로 작동하는지 확인하기 위해 다양한 입력 값을 테스트해보는 것이 중요합니다. 아래는 몇 가지 입력 예시와 그에 대한 최대 공약수입니다:
- a = 48, b = 18 → GCD = 6
- a = 101, b = 10 → GCD = 1
- a = 56, b = 42 → GCD = 14
- a = 24, b = 36 → GCD = 12
위의 예시들은 서로 다른 경우의 수로, 다양한 조합에 대해 최대 공약수를 구하는 과정을 확인할 수 있습니다. 각 조합에 대해 코드의 결과값이 정확한지 검증해보는 것을 잊지 마세요.
6. 비슷한 문제 해결 접근
최대 공약수 문제와 유사한 문제로는 “최소 공배수(Lowest Common Multiple, LCM)”를 구하는 문제가 있습니다. LCM은 두 수 a와 b에 대해 다음과 같은 관계가 성립합니다:
LCM(a, b) = (a * b) / GCD(a, b)
이 관계를 바탕으로, 주어진 두 수의 최소 공배수를 간단히 구할 수 있습니다. 따라서, 최대 공약수 문제를 이해하고 활용하면 최소 공배수 문제도 수월하게 해결할 수 있습니다.
7. 마치며
이번 강좌를 통해 최대 공약수 문제를 해결하는 방법을 배웠습니다. 유클리드 호제법의 이해와 자바 코드 구현을 통해 알고리즘 문제 해결 능력을 향상시키길 바랍니다. 다양한 문제를 연습하고 추가적인 알고리즘과 자료구조를 학습함으로써, 코딩 테스트에서 좋은 결과를 얻기를 바랍니다.
감사합니다!