백준 5618번 파이썬

문제 링크

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

5618번: 공약수

 

시간 제한 / 메모리 제한

1 초

256 MB

 

문제

자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 10^8 이하이다.

출력

입력으로 주어진 n개 수의 공약수를 한 줄에 하나씩 증가하는 순서대로 출력한다.

예제 입력

2
75 125

예제 출력

1
2
11
22

 

풀이 코드

from math import gcd, sqrt
n = int(input())
lst = []

if n == 2:
    a, b = map(int, input().split())
    gcd_ = gcd(a, b)


if n == 3:
    a, b, c = map(int, input().split())
    gcd_ = gcd(gcd(a, b), c)

for i in range(1, int(sqrt(gcd_)) + 1):
    if gcd_ % i == 0:
        lst.append(i)
        if i**2 != gcd_:
            lst.append(gcd_ // i)

lst.sort()

for num in lst:
    print(num)

주어진 두 수 혹은 세 수의 약수를 작은 수 부터 모두 출력하는 문제이다. 

 

두 수 혹은 세 수의 약수는 그들의 최대공약수의 약수이기에 우선 두 수 혹은 세 수의 최대공약수를 구해야 하는데, 이는 Python math library의 gcd를 사용하거나, 유클리드 호제법으로 직접 구할 수 있다.

 

최대공약수를 구한 뒤 약수를 구할 때 주의해야 할 점은 자연수의 크기가 최대 10^8 즉 100,000,000 까지 갈 수 있다는 것이다.

 

단순한 컴퓨터 연산 횟수 공식으로 1초에 1억 번 연산한다는 공식이 있는데, 만약 두 자연수 모두 100,000,000인 테스트 케이스가 있다면 두 수의 최대공약수 또한 100,000,000일 것이며, 최대공약수의 모든 약수를 알아내기 위해 1에서 1억까지 모두 탐색했을 때는 총 1억번 이상의 연산을 수행해 O(n)의 시간 복잡도를 가진다. 그리고 이는 시간초과를 야기할 수 있다.

 

더욱 효율적인 알고리즘으로는 반복문으로 1부터 최대공약수의 제곱근 까지 탐색하며 약수를 구한 뒤, 다시 한 번 이 약수들로 최대공약수를 나누어 그 몫을 취하는 방법이 있으며, 이는 O(√n)의 시간 복잡도를 가진다.

예상대로 O(n) 시간 복잡도의 알고리즘으로는 시간초과, O(√n)의 시간 복잡도를 가진 알고리즘은 정답이었다.

 

참고자료

 

https://minnit-develop.tistory.com/16

[Algorithm/Python] 파이썬 약수 구하기 (시간복잡도 줄여보기)

https://kbw1101.tistory.com/32

[알고리즘] 효율적으로 약수를 찾는 알고리즘

https://doodle-ns.tistory.com/32

[노트] 모든 약수를 구하는 알고리즘은 O(sqrt(n))이다.

https://wikidocs.net/106252

04-01 math.gcd - 최대공약수

https://needneo.tistory.com/77

[Python] 파이썬에서 루트(제곱근) 계산 방법