백준 2702번 [초6 수학](C++) -yes6686- 티스토리

백준 문제 풀이: 2702 (초6 수학)

---

문제 링크: https://www.acmicpc.net/problem/2702

문제 설명:

두 정수 a와 b가 주어졌을 때, **최소공배수**(LCM)와 **최대공약수**(GCD)를 구하는 문제입니다. 여러 개의 테스트 케이스를 입력받고 각각의 결과를 출력해야 합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

// 최대공약수(GCD)를 구하는 함수: 유클리드 호제법 사용
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 최소공배수(LCM)를 구하는 함수
int lcm(int a, int b) {
    return a * b / gcd(a, b); // a와 b의 곱을 GCD로 나눈 값
}

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

    int T;
    cin >> T; // 테스트 케이스의 수 입력

    while (T--) {
        int a, b;
        cin >> a >> b; // 두 정수 입력
        cout << lcm(a, b) << ' ' << gcd(a, b) << '\n'; // LCM과 GCD 출력
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 최대공약수(GCD): - **유클리드 호제법**을 사용하여 두 수의 최대공약수를 구합니다. - gcd(a, b) = gcd(b, a % b)의 성질을 이용해 재귀적으로 계산합니다.
• 최소공배수(LCM): - 두 수의 곱을 최대공약수로 나누어 최소공배수를 구합니다: LCM(a, b) = (a × b) / GCD(a, b)
• 여러 테스트 케이스 처리: - while (T--)를 사용하여 각 테스트 케이스를 반복 처리합니다.

시간 복잡도 분석

• GCD 계산: 유클리드 호제법은 **O(log(min(a, b)))** 시간 복잡도를 가집니다.
• LCM 계산: GCD를 이용해 최소공배수를 계산하므로 추가 연산은 **O(1)**입니다.
• 총 시간 복잡도: **O(T ⋅ log(min(a, b)))**, 여기서 T는 테스트 케이스의 수입니다.

---

결과

각 테스트 케이스마다 두 수의 **최소공배수**와 **최대공약수**를 출력합니다.

• 입력 예시:

  3  
  6 9  
  2 5  
  100 10

• 출력 예시:

  18 3  
  10 1  
  100 10

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!