[Python] 유클리드 호제법을 이용한 최대공약수와 최소공배수 구하기

 

 

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

 

 

오늘도.. 문제를 풀다가.. 음.. 백퍼 나중에 또 찾고 공부하게 생겼네 싶은 문제라서 정리를 해둬본다.. 나중에 다시 풀게 되면... 시간 낭비 말고 잘 기억해내거나 이 글을 찾아서 바로 기억나길 바라며...

 

 

✳️ 유클리드 호제법

• 두 수의 최대공약수(gcd)는 작은 수(b)와 큰 수(a)를 작은 수(b)로 나눈 나머지(r)의 최대공약수(gcd)와 같다.

🥸 정리
a > b인 두 자연수 a, b에 대하여,
q = a // b (a를 b로 나는 몫)
r = a % b (a를 b로 나눈 나머지)
a = qb +r
gcd(a, b) = gcd(b, r)
=> a를 b로 나눈 나머지 r을 구하고 b를 r로 나눈 나머지를 구하는 과정을 반복하다가 나머지가 0이 되는 순간 b는 최대공약수가 된다.

 

🧐 예시 48과 18의 최대공약수를 구하기

1단계 : 두 수 중 큰 수를 작은 수로 나눔

• 48을 18로 나눕니다.
• 48 ÷ 18 = 2 (몫) ... 12 (나머지)
• 48 = 18 X 2 + 12
• 이제 문제는 18과 12의 최대공약수를 찾는 것으로 줄어듬

 

2단계 : 이전 단계의 나머지를 이용해 다시 나눗셈

• 18을 12로 나눕니다.
• 18 ÷ 12 = 1 (몫) ... 6 (나머지)
• 18 = 12 X 1 + 6
• 이제 문제는 12와 6의 최대공약수를 찾는 것으로 줄어듬

 

3단계: 나머지가 0이 될 때까지 이 과정을 반복

• 12를 6으로 나눕니다.
• 12 ÷ 6 = 2 (몫) ... 0 (나머지)
• 12 = 6 X 2 + 0
• 나머지가 0이 되었으므로, 이때 작은 수인 6이 48과 18의 최대공약수

 

 

✳️ 코드 작성 및 해석

# 최대공약수
def gcd(n, m):
    # m이 0이면 최대공약수는 n
    if m == 0:
        return n
    # n을 m으로 나누었을 때 0이면 최대공약수는 m
    if n % m == 0:
        return m
    # 그 외의 경우는 유클리드 호제법을 이용한 재귀적 호출
    else:
        return gcd(m, n % m)
    
# 최소공배수    
def lcm(n, m):
    # 수학적으로 LCM(n, m) * GCD(n, m) = n * m이 성립
    return n * m // gcd(n, m)
 
def solution(n, m):
    answer = []
    answer.append(gcd(n, m))
    answer.append(lcm(n, m))
    
    return answer

 

1️⃣ gcd(n, m) 함수: 최대공약수 계산

• 입력: 두 개의 정수 n과 m
• 출력: 두 수의 최대공약수(GCD)

코드 설명:

• 기본 조건:
  • 만약 m이 0이면, n이 최대공약수. 왜냐하면 한 수가 0일 때, 최대공약수는 다른 수가 되기 때문
  • 이 경우, 함수는 n을 반환하고 종료
• 유클리드 호제법 적용:
  • 유클리드 호제법에 따르면, gcd(n, m)은 gcd(m, n % m)과 같음
  • 여기서 % 연산자는 n을 m으로 나눈 나머지를 의미
  • 이 과정을 재귀적으로 반복하여, 결국 나머지가 0이 될 때 m이 최대공약수가 됨
• 예시:
  • 예를 들어, gcd(48, 18)을 계산해보면
    1. gcd(48, 18)을 호출
    2. gcd(18, 48 % 18) → gcd(18, 12)로 변경
    3. gcd(12, 18 % 12) → gcd(12, 6)로 변경
    4. gcd(6, 12 % 6) → gcd(6, 0)로 변경
    5. 이 시점에서 m이 0이므로, gcd(6, 0)은 6을 반환

 

2️⃣ lcm(n, m) 함수: 최소공배수 계산

• 입력: 두 개의 정수 n과 m
• 출력: 두 수의 최소공배수(LCM)

코드 설명:

• LCM 계산:
  • 두 수의 최소공배수는 n * m을 두 수의 최대공약수(GCD)로 나눈 값과 같음
  • 따라서, lcm(n, m)은 n * m // gcd(n, m)으로 계산 됨
• 왜 이런 방식이 가능한가?
  • 최소공배수(LCM)는 두 수가 공통적으로 나누어 떨어지는 가장 작은 수
  • 수학적으로, LCM(n, m) * GCD(n, m) = n * m이 성립하므로,
    이를 재정리하면 LCM(n, m) = n * m // GCD(n, m)가 됨

 

3️⃣ solution(n, m) 함수: GCD와 LCM 반환

• 입력: 두 개의 정수 n과 m
• 출력: n과 m의 최대공약수(GCD)와 최소공배수(LCM)가 담긴 리스트

코드 설명:

• 리스트 생성 및 값 추가:
  • answer라는 빈 리스트를 생성
  • gcd(n, m)을 호출하여, 반환된 최대공약수를 리스트에 추가
  • lcm(n, m)을 호출하여, 반환된 최소공배수를 리스트에 추가
• 결과 반환:
  • answer 리스트에는 첫 번째 요소로 GCD, 두 번째 요소로 LCM이 들어가게 되고 이 리스트를 반환