[Baekjoon 문제풀이] 2609 - 최대공약수와 최소공배수 (Python 3)

Baekjoon 문제풀이

서론

본 포스팅 시리즈는 필자가 Baekjoon 문제를 풀면서 정리한 코드나 이론을 올리는 포스팅이다.
대부분의 설명은 코드의 주석으로 기재되어있으니 참고바란다.

문제

Baekjoon 2609번 - 최대공약수와 최소공배수:
https://www.acmicpc.net/problem/2609

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

해법

이번 문제는 주어진 두 수의 최대공약수(이하 GCD)와 최소공배수(이하 LCM)를 구하는 문제다. LCM은 GCD를 구하면 간단한 계산( (LCM) = (두 수의 곱) / (GCD) )으로 쉽게 구할 수 있기 때문에, 여기서 핵심과제는 GCD를 효율적으로 구하는 것이다.

GCM을 구하기 위해 주어진 두 수에 2부터 두 수중 작은 값까지 직접 나눠보면서 구할 수도 있겠지만 이러한 방법은 O(N)의 시간복잡도를 가진다. 주어진 수가 작다면 문제가 되진 않겠지만 그렇다고 효율적인 방법이다라고 하기엔 문제가 있다. 그래서 우리는 "유클리드 호제법(Euclidean Algorithm)"이라는 방법을 통해서 O(logN)의 시간복잡도로 이 문제를 해결할 것이다.

유클리드 호제법이란, 두 수의 GCD를 구하는 알고리즘이다. 큰 컨셉은 수를 Moduler 연산하여 나머지가 0이 될때까지 계산하여 GCD를 구하는 것인데, 아래 예시를 참고하길 바란다.

예) 24, 18의 GCD

24 mod 18 = 6
18 mod 6 = 0
∴ (24, 18의 GCD) = 6

풀이

참고자료

위키피디아 - 유클리드 호제법:
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전