1. 유클리드 호제법이란?
유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수(GCD, Greatest Common Divisor)를 계산하는
효율적인 방법입니다. 이 방법은 고대 그리스의 수학자 유클리드가 그의 저서 원론에서 처음으로 제시한 알고리즘입니다.
두 정수 a, b의 최대공약수는 다음과 같은 성질을 갖습니다:
- gcd(a, 0) = a
- gcd(a, b) = gcd(b, a mod b)
이 두 가지 성질을 이용하여 최대공약수를 반복적으로 계산할 수 있습니다. 유클리드 호제법의 시간 복잡도는
O(log(min(a, b)))로 매우 효율적입니다.
2. 유클리드 호제법의 예시
두 정수 48과 18의 최대공약수를 구해보겠습니다.
gcd(48, 18)
1. 48 mod 18 = 12
2. gcd(18, 12)
3. 18 mod 12 = 6
4. gcd(12, 6)
5. 12 mod 6 = 0
6. gcd(6, 0) = 6
따라서, 48과 18의 최대공약수는 6입니다.
3. 유클리드 호제법을 활용한 문제
문제: 두 수의 최대공약수 구하기
주어진 두 정수 a, b에 대해, 두 수의 최대공약수를 구하는 함수를
작성하세요. 스위프트를 사용하여 구현해봅시다.
문제 조건
- 0 < a, b < 231
- 함수의 반환 값은 두 수의 최대공약수입니다.
4. 문제 해결 과정
주어진 문제를 해결하기 위해 스위프트 언어로 구현해보겠습니다.
먼저, 이 문제를 해결하기 위한 함수의 틀을 정의하겠습니다.
func gcd(a: Int, b: Int) -> Int {
// a와 b가 0일 경우 최대공약수 계산
if b == 0 {
return a
} else {
// 재귀를 통해 gcd 계산
return gcd(b, a % b)
}
}
위의 함수를 통해 두 수 a와 b의 최대공약수를 구할 수 있습니다. 여기서 a는 두 수 중 하나,
b는 다른 수이며, 이 함수는 b가 0이 될 때까지 재귀적으로 호출됩니다.
b가 0이 되는 순간, a가 최대공약수로 반환됩니다.
4.1. 예제 코드
아래는 유클리드 호제법을 사용하여 최대공약수를 구하는 전체 코드입니다.
func gcd(a: Int, b: Int) -> Int {
if b == 0 {
return a
} else {
return gcd(b, a % b)
}
}
// 예제 실행
let a = 48
let b = 18
let result = gcd(a: a, b: b)
print("최대공약수: \(result)") // 결과: 최대공약수: 6
5. 스위프트로 구현하는 유클리드 호제법
다음은 유클리드 호제법을 스위프트의 반복문으로 구현한 예제입니다.
때로는 재귀 호출보다는 반복문을 사용하는 것이 메모리 사용 측면에서 더 효율적일 수 있습니다.
func gcdIterative(a: Int, b: Int) -> Int {
var a = a
var b = b
while b != 0 {
let temp = b
b = a % b
a = temp
}
return a
}
// 예제 실행
let resultIterative = gcdIterative(a: a, b: b)
print("반복문을 통한 최대공약수: \(resultIterative)") // 결과: 반복문을 통한 최대공약수: 6
5.1. 다양한 사례로 연습하기
이 함수들을 다양한 정수 쌍에 적용하여 연습할 수 있습니다.
예를 들어, 56과 98의 최대공약수, 101과 103의 최대공약수 등 여러 경우를 시도해보세요.
print("gcd(56, 98) = \(gcd(56, 98))") // 결과: 14
print("gcd(101, 103) = \(gcd(101, 103))") // 결과: 1
6. 결론
유클리드 호제법은 최대공약수를 구하는 간단하지만 매우 효과적인 알고리즘입니다.
스위프트에서 이를 구현하는 방법을 살펴보았습니다. 반복문과 재귀 두 가지 방법을 모두 익힐 수 있었는데요,
때에 따라 어떤 방식이 더 효율적인지 고민해보는 것이 좋습니다.
이러한 알고리즘은 다양한 프로그래밍 대회와 코딩 테스트에서 자주 출제되므로,
충분히 연습하여 익숙해지는 것이 중요합니다.
유클리드 호제법뿐만 아니라 여러 가지 알고리즘과 문제 해결 방법들을 공부해보며
코딩 실력을 더욱 향상시키길 바랍니다. 감사합니다!