TIL_20250311_호제법

문제 설명

• 문제: 두 개의 자연수(1 이상 1,000,000 이하)를 입력받아, 두 수의 최대공약수(GCD)와 최소공배수(LCM)를 구하는 함수를 작성합니다.
• 예시:
  • 입력: 3, 12
  • 출력: [3, 12]
  • 설명: 3과 12의 최대공약수는 3, 최소공배수는 12입니다.

---

호제법 (유클리드 호제법)

• 기본 원리:
  두 수 (a)와 (b) ((a geq b))가 있을 때,
  [
  gcd(a, b) = gcd(b, a mod b)
  ]

• 과정:

  1. (b)가 0이면, 최대공약수는 (a)입니다.
  2. (b)가 0이 아니라면, (a)를 (b)로 나눈 나머지 (r)을 구합니다.
  3. 이제 (a = b), (b = r)로 대체하고 반복합니다.
  4. 최종적으로 나머지가 0이 될 때의 (a)가 최대공약수가 됩니다.

• 예시:

  • (a = 48), (b = 18)인 경우:
    • (48 mod 18 = 12) → (gcd(48, 18) = gcd(18, 12))
    • (18 mod 12 = 6) → (gcd(18, 12) = gcd(12, 6))
    • (12 mod 6 = 0) → 최대공약수는 6

• 최소공배수 계산:
  두 수의 곱을 최대공약수로 나누면 최소공배수가 구해집니다.
  [
  text{LCM} = frac{a times b}{gcd(a, b)}
  ]

---

TIL (Today I Learned)

• 오늘 배운 점:
  • 문제 해결 전략: 두 수의 최대공약수와 최소공배수를 구하는 문제를 해결하기 위해 먼저 유클리드 호제법을 활용하여 최대공약수를 계산하고, 이를 기반으로 최소공배수를 도출하는 방법을 익혔습니다.
  • 호제법의 장점:
    • 간단한 나눗셈 연산만으로 문제를 점점 작게 만들어 효율적으로 최대공약수를 찾을 수 있습니다.
    • 반복 과정을 통해 복잡해 보이는 문제를 간결하게 해결할 수 있다는 점이 인상적이었습니다.
  • 실제 활용:
    • 이 알고리즘은 단순한 수학 문제뿐만 아니라, 다양한 분야에서 두 값의 공통 요소를 찾는 데 유용하게 사용될 수 있습니다.
    • 최소공배수를 구하는 방법도 기억해두면, 관련 문제 해결에 도움이 됩니다.