백준 알고리즘 2609번: 최대공약수와 최소공배수

문제 정보

---

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

 

 

핵심

---

유클리드 호제법을 이용한 최대공약수와 최소공배수를 구한다

유클리드 호제법에 대한 간단한 설명은 다음 게시물에서 확인할 수 있다

유클리드 호제법: 두 수의 최대공약수 구하기

 

 

풀이

---

재귀호출을 사용한 풀이

from sys import stdin
N, M = map(int, stdin.readline().split())

def GCD(A, B):
    r = A % B
    if r == 0:
        return B
    return GCD(B, r)

gcd = GCD(N, M)
print(gcd)
lcm = N*M/gcd
print(int(lcm))

유클리드 호제법에 대한 알고리즘을 알고 있다면, 해당 문제는 쉽게 풀이할 수 있을 것이다

위 풀이는 함수의 재귀호출을 통한 풀이이며 재귀호출 없이 단순 반복으로도 문제를 풀이할 수 있다

 

단순 반복을 사용한 풀이

from sys import stdin
N, M = map(int, stdin.readline().split())
mul = N * M
while N % M != 0:
    N, M = M, N % M

print(M)
print(mul//M)

위와 똑같은 식이지만 더 간결하다

N과 M의 곱을 미리 저장해놓고, N을 M으로 치환, M을 N%M으로 치환해가며 반복을 계속하다가

N%M이 0이 되는 시점에서 멈추고 M(GCD)를 출력해주면 된다

 

 

고찰

---

이런 공식들은 알아두는 것이 좋을 것 같아서 위 링크에 정리하였다

꾸준히 보고 외우도록 노력해야겠다는 생각이 들었다

 

참고

---

GitHub - dduneon/CodingTestPy