Silver V 난이도 문제를 C++로 풀이한 내용입니다. 두 개의 큰 정수가 주어졌을 때, 이 두 수의 최소공배수(LCM)를 구하는 문제입니다.

백준 13241: 최소공배수

Silver V 난이도 문제를 C++로 풀이한 내용입니다. 두 개의 큰 정수가 주어졌을 때, 이 두 수의 최소공배수(LCM)를 구하는 문제입니다.

문제 소개

문제 번호: 13241
문제명: 최소공배수
난이도: Silver V
사용 언어: C++
실행 시간: 0 ms
메모리: 2020 KB
문제 요약: 두 개의 양의 정수 A와 B가 주어질 때, A와 B의 최소공배수를 구하여 출력하는 문제입니다. 입력되는 두 정수는 매우 클 수 있으므로, long long int 타입을 사용하여 오버플로우에 대비해야 합니다.

접근 방법

이 문제를 해결하기 위해 가장 먼저 떠올릴 수 있는 접근 방법은 최소공배수(LCM)를 구하는 공식을 활용하는 것입니다.

두 양의 정수 A와 B에 대해, 최대공약수(GCD)와 최소공배수(LCM) 사이에는 다음과 같은 중요한 관계가 성립합니다.

$LCM (A, B) = \frac{∣ A \times B ∣}{GCD ( A , B )}$

따라서, 이 문제를 해결하기 위해서는 먼저 두 수의 최대공약수를 구하는 알고리즘을 구현해야 합니다. 최대공약수를 구하는 가장 효율적인 방법으로는 **유클리드 호제법(Euclidean Algorithm)**이 있습니다.

왜 이 방법을 선택했는가?

수학적 관계 활용: LCM과 GCD 사이의 명확한 수학적 관계를 이용하면 복잡한 계산 없이 LCM을 구할 수 있습니다.
효율적인 GCD 계산: 유클리드 호제법은 매우 빠르고 효율적으로 최대공약수를 계산할 수 있는 알고리즘으로, 큰 수에 대해서도 성능 저하가 적습니다.
오버플로우 방지: 단순히 A * B를 먼저 계산하면 두 수의 곱이 long long int 범위를 넘어설 수 있습니다. (A / GCD(A, B)) * B 순서로 계산하면 중간 결과의 크기를 줄여 오버플로우 위험을 낮출 수 있습니다. GCD(A, B)는 항상 A의 약수이므로 A / GCD(A, B)는 정수가 되기 때문입니다.

풀이 과정

입력: 두 개의 큰 정수 A와 B를 입력받습니다. long long int 타입을 사용하여 범위를 충분히 확보합니다.
최대공약수(GCD) 계산: 유클리드 호제법을 사용하여 A와 B의 최대공약수를 계산하는 함수(gcd)를 구현합니다.
- gcd(a, b) 함수는 b가 0이 될 때까지 a를 b로 나눈 나머지를 b에, 기존 b 값을 a에 저장하며 반복합니다.
- gcd(a, b) == gcd(b, a % b)라는 성질을 이용합니다.
- b가 0이 되면, a에 남아있는 값이 최대공약수입니다.
최소공배수(LCM) 계산: lcm(a, b) 함수를 구현합니다.
- 앞서 설명한 공식 LCM(a, b) = (a / gcd(a, b)) * b를 사용하여 최소공배수를 계산합니다. 곱셈 전에 나눗셈을 먼저 수행하여 오버플로우 가능성을 줄입니다.
출력: 계산된 최소공배수 값을 출력합니다.

핵심 아이디어

두 수의 최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같다는 성질을 이용합니다.
유클리드 호제법으로 최대공약수를 효율적으로 구합니다.
오버플로우 방지를 위해 (a / gcd(a, b)) * b 순서로 계산합니다.

주의할 점

입력되는 두 정수가 매우 클 수 있으므로, 반드시 long long int 타입을 사용해야 합니다.
최소공배수를 계산할 때 (a * b) / gcd(a, b) 순서로 계산하면 a * b에서 오버플로우가 발생할 수 있으므로, (a / gcd(a, b)) * b 형태로 계산하는 것이 안전합니다.

코드 설명

#include<bits/stdc++.h>
using namespace std;

// a와 b의 최대공약수를 구하는 함수 (유클리드 호제법)
long long int gcd(long long int a, long long int b) {
    while (b != 0) {           // 나머지가 0이 될 때까지 반복
        long long int r = a % b;         // a를 b로 나눈 나머지 r 계산
        a = b;                 // a를 b로 바꿔서 다음 반복 준비
        b = r;                 // b를 나머지 r로 바꿔서 다음 반복
        // 핵심: GCD(a, b) == GCD(b, r) 성질 이용
    }
    return a;                  // 나머지가 0이 되면 a가 최대공약수
}

// a와 b의 최소공배수를 구하는 함수
long long int lcm(long long int a, long long int b) {
    // 핵심 원리: LCM(a, b) = (a*b) / GCD(a, b)
    return (a / gcd(a, b)) * b;  // a*b / GCD 순서로 계산하면 overflow 위험 줄임
} // (a / gcd(a, b))는 항상 정수
  // 이유: gcd(a, b)는 a와 b를 동시에 나누는 수니까, a를 gcd로 나누면 나머지가 0임 → 정수 보장
  // * b 순서를 나누기 먼저 한 것도 overflow 방지용 트릭.

int main(){
        long long int A, B;
        cin >> A >> B;
        cout << lcm(A, B) << '\n';
}

주요 부분 설명

#include<bits/stdc++.h>: C++ 표준 라이브러리의 대부분을 포함하는 헤더 파일입니다. 입출력(cin, cout), 수학 함수 등을 사용할 수 있게 합니다.
using namespace std;: std 네임스페이스를 사용하겠다고 선언하여 std::cin 대신 cin 등으로 사용할 수 있게 합니다.
long long int gcd(long long int a, long long int b): 두 long long int 타입의 정수 a와 b를 받아 최대공약수를 반환하는 함수입니다.
- while (b != 0): 유클리드 호제법의 핵심 루프입니다. b가 0이 될 때까지 반복합니다.
- long long int r = a % b;: a를 b로 나눈 나머지를 r에 저장합니다.
- a = b; b = r;: 다음 유클리드 호제법 단계로 넘어가기 위해 a와 b의 값을 갱신합니다.
- return a;: b가 0이 되었을 때 a에 저장된 값이 최대공약수입니다.
long long int lcm(long long int a, long long int b): 두 long long int 타입의 정수 a와 b를 받아 최소공배수를 반환하는 함수입니다.
- return (a / gcd(a, b)) * b;: LCM(a, b) = (a / GCD(a, b)) * b 공식을 적용합니다. a를 gcd(a, b)로 먼저 나누어 중간 값의 크기를 줄여 오버플로우를 방지합니다.
int main(): 프로그램의 메인 함수입니다.
- long long int A, B;: 두 개의 long long int 변수를 선언합니다.
- cin >> A >> B;: 표준 입력으로부터 두 정수를 읽어 A와 B에 저장합니다.
- cout << lcm(A, B) << '\n';: lcm 함수를 호출하여 계산된 최소공배수를 표준 출력으로 내보내고, 줄바꿈 문자를 추가합니다.

복잡도 분석

시간 복잡도:
- 유클리드 호제법을 이용한 GCD 계산은 입력값의 자릿수에 비례하여 매우 빠르게 수행됩니다. 대략 $O (lo g (min (a, b)))$ 의 시간 복잡도를 가집니다.
- LCM 계산은 GCD 계산과 곱셈, 나눗셈 연산으로 이루어져 있어, GCD 계산의 복잡도를 따릅니다.
- 따라서 전체 시간 복잡도는 $O (lo g (min (A, B)))$ 입니다.
공간 복잡도:
- GCD 함수와 LCM 함수 모두 몇 개의 변수만 사용하므로 공간 복잡도는 $O (1)$ (상수 공간)입니다.

배운 점

이 문제를 통해 다음과 같은 점들을 배울 수 있었습니다.

LCM과 GCD의 관계: 두 수의 최소공배수는 최대공약수를 이용해 효율적으로 계산할 수 있다는 중요한 수학적 관계를 다시 한번 익혔습니다.
유클리드 호제법의 활용: 최대공약수를 구하는 가장 효율적인 방법인 유클리드 호제법을 실제로 구현하고 활용하는 방법을 익혔습니다.
오버플로우 방지 기법: 큰 수를 다룰 때 발생할 수 있는 오버플로우 문제를 어떻게 수학적 연산 순서를 조절하여 방지할 수 있는지 배웠습니다. (a / gcd) * b 형태의 계산이 (a * b) / gcd보다 안전하다는 것을 체감했습니다.
long long int의 중요성: 매우 큰 정수를 다루어야 하는 문제에서는 int 대신 long long int와 같은 더 큰 자료형을 사용해야 한다는 점을 명확히 인지했습니다.

이 문제는 기본적인 수학 지식과 효율적인 알고리즘 구현 능력을 요구하는 좋은 문제였습니다. 특히, 오버플로우를 고려한 코드 작성 습관을 기르는 데 도움이 되었습니다.