[Swift_Programmes] 최대공약수와 최소공배수 ⭐ / 유클리드 호제법, 재귀함수 반복문

 

프로그래머스 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

---

💡 내가 제출한 풀이

func gcdFunc(_ n:Int, _ m:Int) -> Int {
    if m == 0 {
        return n
    } else {
        return gcdFunc(m, n % m)
    }
}
func lcmFunc(_ n:Int, _ m:Int) -> Int {
    return (n*m) / gcdFunc(n,m)
}
func solution(_ n:Int, _ m:Int) -> [Int] {
    return [gcdFunc(n,m), lcmFunc(n,m)]
}

 

---

💡 풀이 과정

 

입력받은 두 수의 최대공약수, 최소공배수를 구하는 문제이다

 

---

유클리드 호제법 (유클리드 알고리즘)

2개의 자연수를 사용해서 최대공약수를 구하는 알고리즘

호제법의 호는 서로 호(互)와 나누다, 덜다라는 뜻의 덜 제(除)를 써 서로 즉 두 수를 나눈다는 뜻

 

> 예시

1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어 떨어진다.

따라서, 최대공약수는 21이다.

78696과 19332의 최대공약수를 구하면,

    78696 ＝ 19332×4 ＋ 1368
    19332 ＝ 1368×14 ＋ 180
     1368 ＝ 180×7 ＋ 108
      180 ＝ 108×1 ＋ 72
      108 ＝ 72×1 ＋ 36
       72 ＝ 36×2 ＋ 0

따라서, 최대공약수는 36이다.

 

 

최대공약수 구하기 (greatest common divisor)

a % b = r

b % r = x

r % x = q

x % q = p

.

.

.

1.  주어진 숫자 a, b의 나머지를 구한다 
2.  a에는 b를 대입하고 b에는 나머지를 대입한다 
3.  나머지가 0이 될 때까지 (b가 0이 될 때까지) 반복해서 계산한다 

 

이런 공식이 적용된다고 생각해서 while문으로 구현해보았다.

// 최대공약수
func gcdFunc(_ n:Int, _ m:Int) -> Int {
    var r = 0
    var (a,b) = (n,m)
    
    while b != 0 {
        r = a % b
        a = b
        b = r
    }
    return a
}

 

다만 이렇게 하면.. 코드가 좀 길지 않나 싶었다.

코딩은 유구히 간략한게 유행 아니던가

 

반복문을 간략하게 쓸 수 있는 방법에 대해 검색해 보던 중, 재귀함수라는 것을 알게 되었다.

 

---

재귀함수

자신을 정의할 때 자기 자신을 재참조하는 방법

 

함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.

특정 분기에 맞을 때 까지 자기 자신을 계속해서 호출하는데, 주로 반복문을 구현할 때 많이 사용한다고 한다.

for, while 같은 반복문으로 구현 가능한 로직은 모두 재귀함수로 만들 수 있고, 그 반대도 구현할 수 있다.

 

단점

1. 재귀 함수는 함수를 호출할 때마다 스택에 새로운 프레임을 생성한다. 따라서, 스택이 너무 깊어질 경우에는 스택 오버플로우가 발생할 가능성이 있다.
2. 재귀 함수는 함수의 호출이 반복적으로 일어나기 때문에, 일반적으로 반복문을 사용하는 것보다 느리다.

 

> 예시

팩토리얼을 구하는 함수 예제이다.

 

팩토리얼?

자연수 n에 대해서 1부터 n까지의 모든 자연수를 곱한 값

5! == 5*4*3*2*1

Func factorial(_ n: Int) -> Int { 
    if (n == 1) { 
        return 1; 
    } 
    return n * factorial(n-1);
}

 

숫자 n이 입력되었을 때, n이 1이 아니라면 n*factorial(n-1)을 반환한다

그리고 반환된 n*factorial(n-1)값이 다시 factorial 에 n으로 입력되고, 다시 n이 1인지 체크한다.

이렇게 반복을 돌다가 어느 한가지 조건에 부합할 때 탈출할 수 있다.

 

 

재귀함수를 이용한 최대공약수 구하기

계산을 한 값을 담기위해서 만들었던 변수들은 전부 삭제할 수 있다.

 

기존 함수는 while문으로 변수 r에다가 나머지 계산한 값을 담고, a와 b에 값을 재할당 해 주었었다.

while b != 0 {
    r = a % b
    a = b
    b = r
}

 

재귀함수를 사용해서 이 while문을 수정했다.

1. 탈출 조건 = 나머지가 0일때
2. 함수 gcdFunc은 매개변수 2개를 받아온다
3. 재귀함수에서 첫번째 매개변수는 두번째 숫자를 입력하고 두번째 매개변수는 나머지를 계산해서 입력한다

if m == 0 {
    return n
} else {
    return gcdFunc(m, n % m)
}

 

결론적으로..

while b != 0 {
    r = a % b
    a = b
    b = r
}

두개는
같다!!!!!!!

if m == 0 {
    return n
} else {
    return gcdFunc(m, n % m)
}

 

---

최소공배수 구하기 (least common multiple)

a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다

 

위에서 최대공약수를 미리 구했으니 최소공배수를 구할 수 있다.

func lcmFunc(_ n:Int, _ m:Int) -> Int {
    return (n*m) / gcdFunc(n,m)
}