1934번 문제를 풀기 위해 최대공약수(GCD)와 최소공배수(LCM)의 원리를 파고들었습니다. 왜 유클리드 호제법을 사용하는지, 그리고 GCD와 LCM이 어떤 관계를 가지는지 이해하게 되었습니다.

최대공약수(GCD)와 최소공배수(LCM)의 원리 탐구

학습 주제

오늘 공부한 주제: 최대공약수(GCD)와 최소공배수(LCM)의 수학적 원리
대화 제목: 최대공약수 최소공배수 원리
학습 날짜: 2026년 2월 3일

질문과 탐구

"1934번 문제 풀이를 위해 최대공약수를 구하고 그걸로 최소공배수를 구하는 것이 맞는지, 그리고 그 원리가 무엇인지"에 대한 궁금증에서 시작했습니다. 특히, 왜 최대공약수(GCD)를 알아야 최소공배수(LCM)를 구할 수 있는지, 그리고 유클리드 호제법이 왜 효율적인지에 대해 탐구했습니다.

주요 질문은 다음과 같았습니다.

최소공배수(LCM)는 어떻게 정의되는가?
LCM과 GCD는 어떤 관계가 있는가?
유클리드 호제법의 원리는 무엇이며, 왜 GCD를 구할 때 사용하는가?
GCD(a, b) = GCD(b, a % b) 성질이 왜 성립하는가?
LCM(a, b) = (a * b) / GCD(a, b) 공식이 어떻게 유도되는가?

핵심 학습 내용

GCD와 LCM의 핵심 원리를 명확히 할 수 있었습니다.

1. 최대공약수 (GCD)와 유클리드 호제법

GCD 정의: 두 수 $a, b$ 의 공통된 약수 중 가장 큰 수입니다.
유클리드 호제법: GCD를 구하는 효율적인 알고리즘입니다.
- 원리: $a > b$ 일 때, GCD(a, b) = GCD(b, a % b) 라는 나머지 성질을 이용합니다.
- 작동 방식: 나머지가 0이 될 때까지 GCD(b, a % b)를 반복하며, 마지막으로 0이 아닌 나머지가 바로 GCD가 됩니다.
- 예시: GCD(18, 12)
  - 18 = 12 * 1 + 6 → GCD(12, 6)
  - 12 = 6 * 2 + 0 → GCD(6, 0)
  - 나머지가 0이 되었으므로, GCD는 6입니다.
GCD(a, b) = GCD(b, a % b)가 성립하는 이유:
- $a = b \cdot q + r$ 일 때, $a$ 와 $b$ 를 동시에 나누는 수 $d$ 는 $b$ 와 $r$ 도 동시에 나눕니다. (즉, $d ∣ a$ 이고 $d ∣ b$ 이면 $d ∣ (a - b \cdot q)$ 이고, $a - b \cdot q = r$ 이므로 $d ∣ r$ 입니다.)
- 반대로 $b$ 와 $r$ 을 동시에 나누는 수 $d$ 는 $a$ 도 나눕니다. (즉, $d ∣ b$ 이고 $d ∣ r$ 이면 $a = b \cdot q + r$ 이므로 $d ∣ a$ 입니다.)
- 따라서, $a$ 와 $b$ 의 공약수 집합과 $b$ 와 $r$ 의 공약수 집합은 동일하므로, 최대공약수 또한 같습니다.

2. 최소공배수 (LCM)와 GCD의 관계

LCM 정의: 두 수 $a, b$ 를 모두 나누는 가장 작은 양의 정수입니다.
GCD와의 관계 공식: $LCM (a, b) = \frac{a \cdot b}{GCD ( a , b )}$
직관적 이해:
- $a$ 와 $b$ 를 곱하면, 이 안에는 두 수의 공약수가 두 번 중복되어 포함됩니다.
- GCD(a, b)로 나누어주면, 중복된 공약수 부분이 한 번만 남게 되어 최소공배수가 됩니다. 마치 "겹친 부분을 펼쳐 바른 상태"와 같습니다.

3. 코드 구현 (C++)

AI는 유클리드 호제법으로 GCD를 구하고, 이를 활용하여 LCM을 구하는 C++ 함수를 제공했습니다.

// a와 b의 최대공약수를 구하는 함수 (유클리드 호제법)
int gcd(int a, int b) {
    while (b != 0) {           // 나머지가 0이 될 때까지 반복
        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의 최소공배수를 구하는 함수
int lcm(int a, int b) {
    // 핵심 원리: LCM(a, b) = a*b / GCD(a, b)
    // overflow 위험을 줄이기 위해 a / gcd(a, b) 먼저 계산
    return (a / gcd(a, b)) * b;
}

a * b를 먼저 계산하면 정수 오버플로우가 발생할 수 있으므로, (a / gcd(a, b)) * b 순서로 계산하는 것이 더 안전합니다. 큰 수를 다룰 때는 long long 자료형을 사용하는 것이 좋습니다.

이해한 내용

이번 대화를 통해 GCD와 LCM에 대한 개념이 명확해졌습니다.

새로 알게 된 것: GCD(a, b) = GCD(b, a % b)의 수학적 증명 과정을 직관적으로 이해하게 되었습니다. 또한, LCM(a, b) = (a * b) / GCD(a, b) 공식이 왜 그렇게 유도되는지에 대한 설명이 매우 명확했습니다.
이전에 몰랐던 것과 연결: 이전에는 단순히 공식을 외워 사용했지만, 이제는 그 공식이 왜 성립하는지에 대한 깊은 이해를 바탕으로 자신감 있게 사용할 수 있게 되었습니다. 나머지 연산의 성질과 약수의 관계를 통해 수학적 원리가 어떻게 실제 알고리즘으로 이어지는지 연결고리를 찾았습니다.
개념 정리:
- GCD: 두 수를 동시에 나누는 가장 큰 수. 유클리드 호제법으로 효율적으로 계산 가능.
- LCM: 두 수를 동시에 나눌 수 있는 가장 작은 수. GCD를 이용해 $(a \cdot b) / GCD (a, b)$ 로 계산 가능.

실전 적용

이 지식은 프로그래밍 문제 해결에 매우 유용하게 적용될 수 있습니다.

적용 분야:
- 코딩 테스트 문제 (예: 1934번 문제처럼 두 수의 LCM을 구해야 하는 경우)
- 수학적 알고리즘 구현
- 자료구조나 알고리즘에서 GCD/LCM 계산이 필요한 부분
실습 계획:
- 주어진 gcd와 lcm 함수를 사용하여 다양한 테스트 케이스에 대한 결과를 확인해볼 것입니다.
- long long 자료형을 사용하여 더 큰 수를 다루는 gcd와 lcm 함수를 직접 구현해볼 계획입니다.
응용 아이디어:
- 여러 개의 수에 대한 GCD 및 LCM을 구하는 함수를 만들어볼 수 있습니다.
- 이 알고리즘을 활용하여 다른 수학적 난제를 해결하는 데 적용해 볼 수 있습니다.

추가 학습 계획

더 깊이 공부하고 싶은 부분:
- 유클리드 호제법의 시간 복잡도 분석.
- 확장 유클리드 알고리즘 (Extended Euclidean Algorithm)을 통한 선형 디오판토스 방정식 해 구하기.
관련 자료 찾기:
- 수학 관련 위키백과 페이지 (유클리드 알고리즘, 최대공약수, 최소공배수).
- 프로그래밍 알고리즘 관련 서적이나 온라인 강의.
다음 학습 주제: 확장 유클리드 알고리즘의 원리와 실제 적용 사례를 탐구해보고 싶습니다.

참고 자료

AI와의 대화에서 언급된 참고 자료:
- GCD(a, b) = GCD(b, a % b) 성질에 대한 수학적 증명
- LCM(a, b) = (a * b) / GCD(a, b) 공식의 유도 과정