BOJ 2609. 최대공약수와 최소공배수 (Python)

BOJ 2609. 최대공약수와 최소공배수

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

풀이1) 유클리드 호제법 쓴 풀이

gcd (great common divisor)

유클리드 호제법: X를 Y로 나눈 나머지 값을 R이라고 했을 때,
X와 Y의 최대공약수는 Y와 R의 최대공약수와 같다.

 

나머지가 0이 될 때 까지 Y와 R의 나머지 연산을 하면 된다.
문제의 예제로 나와있는 24, 18을 예로 들자면
24 % 18 = 6
18 % 6 = 0
이렇게되면 Y값 자리에 있는 6이 최대공약수가 된다.
이것을 소스코드로 옮기면 이렇게 된다.

def gcd(n,m):
    while m:
        n, m = m, n % m
    return n

 

lcm (least common multiple)

최소공배수는 두 값을 곱하고 최대공약수로 나눠주면 된다.

def lcm(n,m):
    return n * m // gcd(n, m)

완성된 소스코드는 아래 "소스코드"의 첫번째에 있다.

 

풀이2) 소인수분해 통한 풀이

무식하게 소인수분해를 한 다음 구하는 방법도 있다.
소인수분해 구하는것 연습할 겸 해봤다.

def get_prime_factor(n) -> dict:
    dic = collections.defaultdict(int)
    i = 2

    while i <= n:
        if n % i == 0:
            dic[i] += 1
            n = n/i
        else:
            i += 1

    return dic

소인수분해한 결과를 딕셔너리에 저장해 주는 함수이다. collections의 defaultdict를 이용하면 빈 값을 초기화 하여 에러 없이 사용 가능하다.

그렇게 되면

dict_items([(2, 3), (3, 1)])
dict_items([(2, 1), (3, 2)])

24, 18에 해당하는 소인수분해 딕셔너리를 얻을 수 있다.
이렇게 구하고 나서 최대공약수는 겹치는 부분중 적은 것, 최소공배수는 둘중에 많은것을 각각 곱해주면 된다. 소스코드는 너무 길어서 아래쪽에만 적어뒀다.

 

풀이3)

원래,, 파이썬의 math모듈을 이용해서 gcd(), lcm()함수로 간단하게 구할 수 있는데 백준에서 돌렸을때 "런타임 에러 (AttributeError)"가 발생한다.
그래서 제출 성공을 못했다 ㅜㅜ 내가 돌렸을땐 잘 돌아가는데 아시는분 알려주세요.. (찾아도 안나와 ㅜㅜ)
어차피 내장 함수를 이용하는 것은 그렇게 좋은 방법은 아니니까(문제 의도가 이것이 아닐 것) 괜찮긴 한데 이유가 궁금..

 

전체 소스코드

1. 유클리드 호제법

def gcd(n,m):
    while m:
        n, m = m, n % m
    return n

def lcm(n,m):
    return n * m // gcd(n, m)

N, M = map(int, input().split())

print(gcd(N, M))
print(lcm(N, M))

2. 소인수 분해

import collections

def get_prime_factor(n) -> dict:
    dic = collections.defaultdict(int)
    i = 2

    while i <= n:
        if n % i == 0:
            dic[i] += 1
            n = n/i
        else:
            i += 1

    return dic

N, M = map(int, input().split())

# 소인수분해
N_prime_factor = get_prime_factor(N)
M_prime_factor = get_prime_factor(M)

# 소인수 가짓수 많은것을 M으로 설정
if len(N_prime_factor) > len(M_prime_factor):
    N_prime_factor, M_prime_factor = M_prime_factor, N_prime_factor

great, least = 1, 1 # 곱할꺼니까 1로 초깃값 설정

# 최대공약수 구하기
great_dic = collections.defaultdict(int)
for k in N_prime_factor.keys():
    great_dic[k] = min(N_prime_factor[k], M_prime_factor[k])

for k, v in great_dic.items():
    great *= pow(k,v)

# 최소공배수 구하기
least_dic = collections.defaultdict(int)
for k in M_prime_factor.keys():
    if k not in N_prime_factor:
        least_dic[k] = M_prime_factor[k]
    else:
        least_dic[k] = max(N_prime_factor[k], M_prime_factor[k])

for k, v in least_dic.items():
    least *= pow(k,v)

print(great)
print(least)

3. 내장함수 사용

import math

N, M = map(int, input().split())
print(math.gcd(N,M))
print(math.lcm(N,M))