꾸준히 개발하기

1초 뒤에 D만큼 움직여야 하고 모든 동생에게 닿을 수 있는 D의 최댓값을 구해야 되는 문제다.

즉, n개의 수 <-> 정수 s 차이의 최대공약수를 구해주면 되는 문제다.

편하게 파이썬의 math.gcd() 함수를 사용했다. gcd() 함수를 자세히 보니 다음과 같이 애스터리스트(*)표시가 있었다.

따라서 거리 차이 리스트를 '*' 표시를 붙여서 함수에 넘겨준 뒤 그 값을 출력하면 되는 문제였다. 파이썬 최고 .. 물론 이 방법이 아니면 유클리드 호제법으로 계속 수를 반복적으로 gcd구해주면 되겠다. 이번에는 파이썬 애스터리스트 문법을 배웠다는 거에 의의를 두고 라이브러리르 쓰겠다 ㅎㅎ

코드는 다음과 같다.

import math

n, s = map(int, input().split())

data = list(map(int, input().split()))
gaps = []

for v in data:
    gaps.append(abs(s - v))

print(math.gcd(*gaps))

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

이번 기회에 파이썬에서 사용 가능한 최대공약수(gcd), 최소공배수(lcm) 구하는 방법을 다 정리해보았다.

가장 베이직한 방법

최대공약수 : 숫자 x,y 중 더 작은 숫자부터 1까지 -1 해가며 x%i == 0 and y%i == 0인 숫자 찾기

최소공배수 : 숫자 x,y 중 더 큰 숫자부터 (x*y)까지 +1 해가며 i%x == 0 and i%y == 0인 숫자 찾기

유클리드 호제법

x,y의 gcd는 y와 r의 gcd와 같다. ( x%y = r)

즉 계속해서 x의 자리에 y값을 대입하고, y에는 x%y 값인 r을 대입하면 x%y == 0 인 순간의 y값이 바로 gcd이다.

최소공배수는 x*y를 위에서 구한 gcd로 나눠주면 된다.

라이브러리 활용

이게 사실 제일 편하다..^^ 파이썬의 math 라이브러리는 인자를 심지어 여러개 받을 수 있는 최대공약수, 최소공배수를 구해주는 함수를 제공한다.

math 라이브러리를 import 해주고 math.gcd( 인자, 인자, ... ) math.lcm( 인자, 인자 ,... ) 해주면 된다.

코드는 다음과 같다.

n, m = map(int, input().split())

# 가장 베이직한 방법
def getGCD_basic(x, y):
    for i in range(min(x, y), 0, -1):
        if x % i == 0 and y % i == 0:
            return i


def getLCM_basic(x, y):
    for i in range(max(x, y), (x * y) + 1):
        if i % x == 0 and i % y == 0:
            return i


# 유클리드 호제법
def getGCD_euclid(x, y):
    while y:
        x, y = y, x % y
    return x


def getLCM_euclid(x, y):
    return (x * y) // getGCD_euclid(x, y)


# 파이썬 라이브러리 활용
import math

print(math.gcd(n, m))
print(math.lcm(n, m))

유클리드 호제법은 정말... 정말 오랜만에 다시 들여다봤다...^^ 수학을 열심히 했던 학생이었는데 이렇게까지 싸그리 까먹을 수 있다니 슬프다. 안 좋은 일이나 빨리 까먹지 이런 수학적 지식만 홀라당 다 까먹어 버렸다.