[BaekJoon 2609][🟤1] 최대공약수와 최소공배수

❓ 문제

백준 2609 - “최대공약수와 최소공배수”

🎯 난이도

Bronze 🟤1

🧠 풀이

1. 내 풀이 (유클리드 호제법)

- 알고리즘

• GCD, LCM, Euclidean algorithm

- 설명

유클리드 호제법을 활용해 최대공약수와 최소공배수를 찾는 방식이다.

사실 최대공약수를 찾는 가장 유명하고 자주 쓰이는 알고리즘을 썼기 때문에 딱히 특별할 것은 없다. 최대공약수를 찾으면, 최소공배수는 쉽게 찾을 수 있다.

유클리드 호제법 알고리즘을 사용하므로 시간 복잡도는 O(log N)이다.

- 코드

내 풀이 코드

#include <iostream>


using namespace std;

int GCD(int iNum1, int iNum2);
int LCM(int iNum1, int iNum2, int iGCD);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iMin{}, iMax{};
    cin >> iMin >> iMax;

    int iGCD{};
    iGCD = GCD(iMin, iMax);

    cout << iGCD << "\n" << LCM(iMin, iMax, iGCD);

    return 0;
}

// 유클리드 호제법을 사용한 GCD 구하기
int GCD(int iNum1, int iNum2)
{
    if(iNum2 == 0) return iNum1;
    return GCD(iNum2, iNum1 % iNum2);
}

// LCM은 두 숫자를 곱하고 GCD로 나눠주면 나온다
int LCM(int iNum1, int iNum2, int iGCD)
{
    return iNum1 * iNum2 / iGCD;
}

---

💭 후기

가장 기본적인 최대공약수, 최소공배수를 구하는 문제라 한 번 되짚어보고자 포스팅을 만들었다.

유클리드 호제법은 이런 상황에서 많이 쓰이기도 하고, 시간 복잡도 또한 피보나치 수열 같은 최악의 경우만 아니라면 O(log N)를 보장하니 잘 기억해두도록 하자.

🔗 참고자료

• 최대공약수, 최소공배수