알고리즘(Swift) - 유클리드 알고리즘

 

유클리드 알고리즘

• 최대 공약수 (GCD, Greatest Common Divisor)를 효율적으로 구하는 알고리즘
• 유클리드 호제법을 코드로 구현한 것
  • https://ko.wikipedia.org/wiki/유클리드_호제법

 

유클리드 호제법

• 두 정수의 최대공약수를 구하는 방법으로, 나눗셈의 나머지를 반복적으로 계산하는 방식

 

호제법

• “서로를 나눈다”라는 뜻
• 큰 수를 작은 수로 나누고 그 나머지를 이용해 반복적으로 계산하는 알고리즘
• GCD(a, b) = GCD(b, a mod b)
• → a mod b : a를 b로 나눈 나머지

 

알고리즘 과정

1. 두 수 a, b를 비교하여 a ≥ b가 되도록 설정
2. a를 b로 나눈 나머지 r = a mod b를 계산
3. a를 b로 b를 r로 대체
4. 나머지 r이 0일 될 때까지 2~3단계를 반복
5. 나머지가 0이 되는 순간의 b가 최대 공약수

 

 

예시

예: GCD(48, 18)

1. a=48, b=18.
2. r = 48 mod 18 = 12
   • a = 18, b = 12 (a를 b(18)로 대체, b를 12(r)로 대체)
3. r = 18 mod 12 = 6
   • a = 12, b = 6
4. r = 12 mod 6 = 0
   • 나머지가 0이므로 b = 6이 최대 공약수

 

시간 복잡도

• O(log N)

 

Swift 코드

func gcd(_ a: Int, _ b: Int) -> Int {
	return a % b == 0 ? b : gcd(b, a % b)
}

→ a % b == 0 이면 b를 반환, 아니면 재귀 호출

 

 

활용 (최소공배수 - LCM 구하기)

• 최대공약수는 최소공배수(LCM)과의 관계를 나타낼 수 있음
• 어떤 수 A와 B의 최소공배수를 구하기 위해서는 두 수의 곱(A x B) 나누기 최대공약수(GCD)를 하면 되기 때문!

// 최대 공약수
func gcd(_ a: Int, _ b: Int) -> Int {
	return a % b == 0 ? b : gcd(b, a % b)
}

// 최소 공배수
func lcm(_ a: Int, _ b: Int) -> Int {
	return a * b / gcd(a, b)
}

 

 

 

 

https://gliver.tistory.com/10

[04강] 유클리드 알고리즘