[TIL 18th] 재귀 & 유클리드 호제법 다시 사용해보기

[문제1] 프로그래머스 최대공배수, 최소공약수 구하기

(링크)

　"어떻게 저 사람들은 재귀를 딱딱 떠올릴수있지?"

재귀라는 개념은 대학교 1학년때 컴공에 대한 만족도를 하드하게 만들었던 개념 중에 하나이다.

　유클리드 호제법(Euclidean Algorithm)은 두 자연수의 최대공약수(Greatest Common Divisior)를 구하는 방식 중 하나이다.

해당 방식의 특징은 재귀방식을 사용했다는 점이고, 최악의 경우에도 시간 복잡도가 O(log(min(A,B)))로 작동한다는 장점이 있다.

　최대공배수(LCM)는 두 수의 곱을 GCD로 나누면 구할 수 있다.

 

유클리드 호제법의 원리는 아래와 같다.

1) A>B인 두 수의 최대공약수를 G라 한다면 (G = GCD(A, B)) → A=𝛼×G, B=𝛽×G (𝛼, 𝛽는 서로소) 라고 할 수 있다.

2) A를 B로 나눌 때의 식을 쓰면 → A = 몫qB + 나머지r 로 표현할 수 있다.

3) 식2)에 식1)을 대입하면 → 𝛼×G = q(𝛽×G) + r 이다.

4) 나머지r을 좌변에 두어 식을 정리하면 → r = 𝛼×G - q(𝛽×G) = (𝛼 - q𝛽)×G = dG (d = 𝛼 - q𝛽)이다.

5) 식3)에 식4)를 대입하면 → 𝛼×G = q(𝛽×G) + dG (d = 𝛼 - q𝛽)

6) 식5)를 G로 나누면 → 𝛼 = q𝛽 + d (d = 𝛼 - q𝛽) 

7) 식6)의 𝛽 와 d 의 최대공약수 G' 가 1을 초과한다고 가정한다. GCD(𝛽,d) = G' > 1, 𝛽=𝛽'×G', d=d'×G'

8) 식2)에 식7)을 대입하면 𝛼 = q𝛽 + d = q(𝛽'×G') + d'×G' = (q𝛽'+d')×G' 이다.

9) 𝛼, 𝛽는 서로소인데(1) 𝛽 와 d 의 최대공약수 G' 가 1을 초과한다고 가정하면 𝛼 = (q𝛽'+d')×G' 𝛽=𝛽'×G' 이 되어 모순이 생긴다.

10) 따라서, 𝛽 와 d 의 최대공약수는 1이다.

11) G𝛽 와 Gd 즉 B와 r의 최대공약수는 G이다. GCD(B, r) = G

12) [재귀] GCD(A, B) = GCD(B, r) = GCD(r, B%r) = ・・・ = G 로 간단하게 바꿀 수 있다.

13) [재귀의 종료조건] 식12) 에서 필연적으로 GCD(X,G)의 상황이 만들어진다. (X = q'G + 0)

GCD(A, B) = GCD(B, r) 의 규칙대로라면 GCD(X,G) = GCD(G,0)이다.

따라서, 두번째 인자가 0이 될 때의 첫번째 인자가 최대공약수이다.

GCD(A, B) = GCD(B, A%B) = GCD(G, 0) = G

유클리드 호제법의 원리 https://www.youtube.com/watch?v=TxdljAFjTNw

[답1] C++ 재귀함수로 구현한 코드

#include <vector>

using namespace std;

int GCD(int a, int b){
    if(b == 0) return a;    // 재귀 탈출
    return GCD(b, a%b);     // 재귀
}

int LCM(int a, int b, int gcd){
    return (a*b/gcd);
}

vector<int> solution(int n, int m) {
    if(n<m) {
        int temp=n;
        n=m;
        m=temp;
    }
    
    int gcd = GCD(n,m);
    int lcm = LCM(n,m,gcd);
    
    vector<int> answer;
    answer.push_back(gcd);
    answer.push_back(lcm);
    return answer;
}

[답2] 조금 더 간결한 코드

#include <vector>

using namespace std;

int gcd(int a, int b){
    return (b ? gcd(b, a%b) : a); // 재귀
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    if(n<m) {
        int temp=n;
        n=m;
        m=temp;
    }
    answer.push_back(gcd(n,m));
    answer.push_back(n*m/answer[0]);
    
    return answer;
}

[답3] 라이브러리 활용

#include <vector>

using namespace std;

int gcd(int a, int b){
    return (b ? gcd(b, a%b) : a); // 재귀
}

vector<int> solution(int n, int m) {
    vector<int> answer;
    
    if(n<m) {
        int temp=n;
        n=m;
        m=temp;
    }
    answer.push_back(gcd(n,m));
    answer.push_back(n*m/answer[0]);
    
    return answer;
}