[백준/C++] 2609번: 최대공약수와 최소공배수 - 브루트 포스 vs 유클리드 호제법

1. 문제 정보

• 문제 번호: 2609번
• 문제 이름: 최대공약수와 최소공배수
• 사용 언어: C++
• 문제 링크: 백준 2609번 바로가기
• 문제 요약: 두 개의 자연수를 입력받아 최대공약수(GCD)와 최소공배수(LCM)를 출력하는 프로그램을 작성하시오.

 

2. 접근 방법 1: 브루트 포스 (정의 그대로 풀기)

지난번에 배운 브루트 포스(Brute Force) 개념을 적용해 보았다.

최대공약수란 말 그대로 "공통된 약수 중 가장 큰 수"이다. 컴퓨터는 계산이 빠르니, 굳이 머리 써서 공식을 찾기보다 모든 약수를 다 구해서 비교하는 방식을 택했다.

1. N의 약수를 모두 구해 리스트(vector)에 넣는다.
2. M의 약수를 모두 구해 리스트에 넣는다.
3. 두 리스트를 이중 반복문으로 비교하며 공통된 약수 중 최댓값(maxNum)을 찾는다.
4. 최소공배수는 구한 최대공약수를 이용해 계산한다.

 

💻 코드 구현 (Brute Force)

#include <iostream>
#include <vector>
#include <algorithm> // max 함수 사용
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> numbers1, numbers2;
    int maxNum = 0; // 최대공약수 (GCD)
    int minNum = 0; // 최소공배수 (LCM)
    
    // 1. n의 모든 약수 구하기
    for(int i = 1; i <= n; i++){
        if(n % i == 0){
            numbers1.push_back(i);
        }
    }

    // 2. m의 모든 약수 구하기
    for(int i = 1; i <= m; i++){
        if(m % i == 0){
            numbers2.push_back(i);
        }
    }

    // 3. 두 리스트를 비교하여 최대공약수 찾기 (Brute Force)
    for(int num1 : numbers1){
        for(int num2 : numbers2){
            if(num1 == num2){
                maxNum = max(num1, maxNum);
            }
        }
    }

    // 4. 최소공배수 구하기
    // n = a * GCD, m = b * GCD 일 때, LCM = a * b * GCD
    int a = n / maxNum;
    int b = m / maxNum;
    minNum = a * b * maxNum;

    cout << maxNum << endl;
    cout << minNum << endl;
}

 

3. 접근 방법 2: 유클리드 호제법 (수학적 최적화) - 이산수학

브루트 포스로도 정답을 맞혔지만, 만약 입력되는 숫자가 10억, 100억처럼 매우 커진다면 반복문을 끝까지 돌리기 힘들 것이다. 이때 사용하는 훨씬 효율적인 알고리즘이 유클리드 호제법(Euclidean Algorithm)이다.

 

핵심 공식

두 자연수 A, B에 대하여 (A > B), A를 B로 나눈 나머지를 R이라고 할 때,

GCD(A, B)는 GCD(B, R)과 같다.

이 과정을 R이 0이 될 때까지 반복하면, 그때의 B가 바로 최대공약수다.

최소 공배수 공식

LCM(A,B) = A*B / GCD(A,B)


수정된 코드

#include <iostream>
using namespace std;
int main() {
     int a,b;
    cin>>a>>b;
    int multi=a*b;

    int gcd,lcm;
    //최대 공약수 구하기
    while(b!=0){
        int r=a%b;
        a=b;
        b=r;
    }

    gcd=a;

    //최소 공배수 구하기
    lcm=multi/gcd;

    cout<<gcd<<"\n"<<lcm;
}

4. 배운 점 & 회고 (TIL)

A. 브루트 포스의 적용

"모든 경우를 다 해본다"는 브루트 포스 방식을 약수 구하기에 적용해 보았다. 숫자가 작을 때는(이 문제는 10,000 이하) 정의 그대로 코드를 짜는 것이 직관적이고 구현하기도 쉽다는 것을 느꼈다.

B. 시간 복잡도의 차이 (O(N) vs O(log N))

• 내 코드(브루트 포스): 1부터 N까지 다 나눠봐야 하므로 시간 복잡도가 $O(N)이다.
• 유클리드 호제법: 나머지를 구하며 숫자가 급격히 줄어들기 때문에 시간 복잡도가 O(log N)이다.
• 알고리즘 문제에서는 N의 크기에 따라 적절한 방법을 선택해야 함을 배웠다.

C. 최소공배수(LCM) 계산 아이디어

 

A X B = GCD X LCM

 

---

이산수학 개념 다시 공부해야겠다..