안녕하세요! 이번 시간에는 코틀린을 활용하여 최대 공약수를 구하는 알고리즘 문제를 다루어 보겠습니다. 최대 공약수(Greatest Common Divisor, GCD)란 두 개 이상의 정수가 공유하는 가장 큰 약수를 의미합니다. 이 문제는 프로그래밍 면접에서 자주 나오는 문제 중 하나입니다. 그럼 문제를 살펴보겠습니다.
문제 설명
주어진 두 정수 A와 B가 있을 때, 이 두 숫자의 최대 공약수를 계산하는 함수를 작성하세요. 예를 들어, A와 B가 각각 48과 18이라면, 최대 공약수는 6입니다.
입력 형식
- 첫 번째 줄에 정수 A가 주어진다. (1 ≤ A ≤ 109)
- 두 번째 줄에 정수 B가 주어진다. (1 ≤ B ≤ 109)
출력 형식
두 정수의 최대 공약수를 출력한다.
문제 접근 방법
최대 공약수를 구하는 방법에는 여러 가지가 있지만, 그 중에서도 유클리드 호제법(Euclidean algorithm)이 가장 유명하고 효율적인 방법입니다. 유클리드 호제법은 다음과 같은 원리를 기반으로 합니다:
- GCD(A, B) = GCD(B, A % B) (B가 0이 될 때까지)
- GCD(A, 0) = A
즉, 두 수 A와 B가 있을 때, B를 A로 나눈 나머지를 구하고, 이 과정에서 B가 0이 되는 경우 A가 최대 공약수임을 알 수 있습니다. 이 알고리즘은 두 수의 크기에 비례하여 매우 빠른 속도로 최대 공약수를 찾을 수 있습니다.
코틀린 구현
이제 위의 알고리즘을 코틀린으로 구현해 보겠습니다. 코드 예시는 아래와 같습니다:
fun gcd(a: Int, b: Int): Int {
return if (b == 0) a else gcd(b, a % b)
}
fun main() {
val a = readLine()!!.toInt()
val b = readLine()!!.toInt()
println(gcd(a, b))
}위 코드는 두 정수를 입력받고 GCD 함수를 통해 최대 공약수를 계산하여 출력하는 방식입니다.
상세 코드 설명
1. 함수 정의
먼저, gcd이라는 이름의 함수를 정의합니다. 이 함수는 두 개의 정수 a와 b를 매개변수로 받습니다.
2. 종료 조건
함수 내부에서는 b가 0인지 확인합니다. 만약 b가 0이면 최대 공약수는 a이므로, a를 반환합니다.
3. 재귀 호출
그렇지 않으면, 재귀적으로 gcd(b, a % b)를 호출합니다. 이 과정을 반복하면서 b가 0이 될 때까지 최대 공약수를 계산합니다.
4. 메인 함수
main 함수에서는 readLine()을 사용하여 사용자로부터 두 개의 정수를 입력받습니다. 이 입력값은 !!를 이용해 null이 아님을 보장하고, toInt()를 호출하여 정수형으로 변환합니다. 그리고 최종적으로 println(gcd(a, b))를 호출하여 결과를 출력합니다.
테스트 케이스
이제 이 알고리즘이 제대로 작동하는지 테스트케이스를 통해 검증하겠습니다. 아래는 몇 가지 테스트 케이스입니다:
| 테스트 케이스 번호 | A | B | Expected Output | 실제 Output |
|---|---|---|---|---|
| 1 | 48 | 18 | 6 | |
| 2 | 56 | 98 | 14 | |
| 3 | 101 | 10 | 1 | |
| 4 | 7 | 13 | 1 |
코드 최적화
위의 구현은 간단하고 이해하기 쉬운 형태입니다. 그러나 조금 더 최적화된 방식으로 구현할 수도 있습니다. 코틀린의 내장 함수와 API를 사용하여, 더욱 줄어든 코드와 성능을 제공합니다. 예를 들어, 코틀린에서는 Math 클래스의 gcd 함수를 사용할 수도 있습니다. 이렇게 하면 코드를 더욱 간결하게 만들 수 있습니다:
fun main() {
val a = readLine()!!.toInt()
val b = readLine()!!.toInt()
println(Math.gcd(a, b)) // Java 8 이상에서 사용하는 방법
}마무리
이번 강좌에서는 코틀린을 사용하여 최대 공약수를 구하는 문제를 다루어 보았습니다. 유클리드 호제법을 통해 간단하면서도 효율적인 방법으로 해결할 수 있음을 알 수 있었습니다.
코딩 테스트 준비에 있어 다양한 문제를 접하고, 이 문제들을 해결하는 과정에서 알고리즘적 사고를 키우는 것이 중요합니다. 다음 코딩 테스트에 성공하기 위해서는 실제 코드를 구현하고, 다양한 상황을 테스트해 보시기 바랍니다.
추가적인 질문이나 주제에 대한 요청이 있다면 댓글로 남겨 주세요! 읽어주셔서 감사합니다!