[Algorithm] Swift 유클리드 호제법 (최대공약수), 그리고 최소공배수

 

 

유클리드 호제법 (최대공약수 구하기)

 

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘임!!

 

호제법이란 말을 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타냄! 

 

2개의 자연수 ( 또는 정식 ) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (이 때는 a > b)

 

a와 b의 최대공약수는 b와 r의 최대공약수와 같음!!! 

 

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때

 

나누는 수가 a와 b의 최대공약수임!!! 

 

말로만 들으면 누구나 모름  🔽 아래를 보면 이해가 됨!! 

 

 

 

마지막에 나머지가 0이 나왔을 때!! 나누는 수가!! GCD임!!

 

GCD는 최대공약수(Greatest Common Divisor)를 말함! 

 

이론은 알았으니깐!!  Swift로 구현해 볼까?? 

 

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

 

요렇게 작성

 

b가 0 이면 a를 리턴해줌!!

 

두 값을 입력받아서 최대공약수를 구해볼까~!!!

 

let n = readLine()!.split(separator: " ").map { Int(String($0))!}

// 입력 24 18

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

print(gcd(n[0], n[1]))

// 6

   

24와 18의 최대공약수인 6이 잘 나옴!!! 

 

🙋‍♂️ 나의 의문 첫째!! 🤔

 

근데 아까 유클리드 호제법 이론을 배웠을 때 (a > b)라는 것을 봤는데

 

그럼 두 개의 숫자를 입력받았을 때 뒷자리 숫자가 더 크면 안 되는 거야???라고 생각이 들것이다!! 

 

한번 해볼까?? 과연?? 

 

 

문제없이 나옴!!!!  왜냐!!! 

 

뒷자리 숫자가 크더라고 나머지를 구하는 과정에서 b가 a로 넘어오기 때문에 

 

a > b 조건을 만들어줌!!! 

 

🙋‍♂️ 나의 의문 둘째!! 🤔

 

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

 

코드를 아무리 봐도 내가 생각하는 while문 or for문과 같은 반복문!!이 없는데

 

어떻게 b가 0일때 까지 반복을 하는 거지?????라는 의문이 들었음!! 

 

자!! 코드를 다시 보면 

 

return gcd(b, a % b)

 

else scope 안에 gcd() 리턴이 되고 있음 

 

이건 재귀 함수라고 함!!

 

재귀 함수는 내 함수 안에서 내 함수를 호출하는 형태임!!

 

위 코드를 보면 gcd() 함수 안에서 gcd를 또 호출하고 있음!!!

 

b가 0일 때까지 gcd를 계속 호출하게 된 거임!!! 

 

 

최대공배수 구하기!! 

 

유클리드 호제법은 두 수의 최대공약수만 구하는 것임!! 

 

그럼 최소공배수(Least Common Multiple)는 어떻게 구함???🤔

 

두 자연수 a와 b의 최대공약수와 최소공배수는 특별한 관계가 있음!!

바로 두 자연수 ab = 최대공약수 * 최소공배수이기 때문!!!!

 

우리는 최대공약수를 이미 구했음!!

 

위 공식을 활용하여  (a*b) / 최대공약수 = 최소공배수임!!

 

func lcm(_ a: Int, _ b: Int) -> Int {
    return (a * b) / gcd(a, b)
}

 

요렇게 구할 수 있음!!! 

 

그러면 한 번에 두 자연수의 최대공약수와 최소공배수를 구해볼까!! 

 

let n = readLine()!.split(separator: " ").map { Int(String($0))!}
// 24 18

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

func lcm(_ a: Int, _ b: Int) -> Int {
    return (a * b) / gcd(a, b)
}

print(gcd(n[0], n[1]))
// 6
print(lcm(n[0], n[1]))
// 72

 

입력으로 24 18을 넣어보면!! 

 

두 수의 최대공약수와 최소공배수가 잘 나옴!!!!!!!!