[Algorithm][Euclidean]유클리드 호제법과 최소공배수, 최대공약수

추상적 자료형(Abstract data type)과 자료구조(Data structure)는 엄밀히 말하면 다르다.

가령 스택의 경우는 추상적 자료형이다. 그 이유는 리스트(List)는 정의만 존재하고 구현은 사용자 마음이다.

그러나 만약 누군가가 연결리스트(Linked List), 혹은 배열리스트(Array List, Vector)를 말한다면 그건 자료구조인 셈이다.

그러나 이런 구분이 애매한 녀석들도 존재하기는 한다.

스택(Stack)같은 녀석이 그 정체인데 스택은 추상적 자료형으로 분류되는게 맞으나 사실상 자료구조라고도 볼 수 있다.

왜냐하면 스택을 구현하는 방식이 배열과 연결리스트 두가지가 존재하긴 하지만 사실상 무조건 배열을 쓰는게 이득이기 때문이다.

그래서 필자의 포스팅에서는 추상적 자료형과 자료구조를 엄밀히 구분하지 않고 모두 자료구조라 논하겠다.

참고:

이 사이트의 예제 문제는 백준 사이트(https://www.acmicpc.net/)를 참조합니다.

선수:

[Recursive]재귀 함수

예제:

백준 최대공약수와 최소공배수(2609)

백준 최소공배수(1934)

사실 최대 공약수와 최소공배수 문제는 여러분들이 지겹도록 고등학교때 풀었다.

가장 쉬운 방식은 유클리드 호제법이라는 것이다.

이 유클리드 호제법이 무엇인지 언급하지는 않겠다.

설명은 여기를 참조하라.

유클리드 호제법을 구현하기 위해서는 재귀를 사용한다.

재귀를 굳이 사용하지 않아도 상관은 없다.

반복문을 사용해도 충분히 구현할 수 있기 때문이다.

유클리드 호제법은 엄밀히 말하면 gcd(최대공약수)를 구하는 식이다.

딱 두가지 기억할건 A를 B로 나눈 나머지가 0이면 최대공약수는 B가 되고

그게 아니라면 A=>B B=>A%B로 두고 다시 함수를 돌리면된다.

여기서 A와 B의 교환법칙은 성립된다.

왜 성립되는지 여러분이 종이에 끄적이면 바로 알게 될 것이다.

gcd를 구하면 이를 바탕으로 lcm(최소공배수)를 구할 수 있다.

최소공배수의 공식은 A*B/gcd(A,B)이다.

이를 표현하면 아래와 같다.

#include <stdio.h>

int A,B;

int gcd(int a,int b){
    if(a%b==0){
        return b;
    }else{
        return gcd(b,a%b);
    }
}

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

int main(){
    scanf("%d %d",&A,&B);
    printf("gcd : %d\n",gcd(A,B));
    printf("lcm : %d",lcm(A,B));
    return 0;
}

이 방법으로 gcd와 lcm을 구할수 있으며,

이보다 간단하고 빠르게 구할수 있는 방법은 존재치 않는다.

따라서 문제에서 요구하는게 최대공배수,최소공약수가 존재한다면 바로 이를 활용해주면되다.