λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

Programming/Algorithm

[Algorithm] μ΅œλŒ€ κ³΅μ•½μˆ˜, μ΅œμ†Œ 곡배수 κ΅¬ν•˜κΈ°

728x90
λ°˜μ‘ν˜•

GCD(Greatest Common Divisor) μ΅œλŒ€ κ³΅μ•½μˆ˜ κ΅¬ν•˜κΈ°

μœ ν΄λ¦¬λ“œ ν˜Έμ œλ²• μ‚¬μš©

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

a = b x q + r 이라고 ν–ˆμ„ λ•Œ, GCD(a, b) = GCD(b, r)λ₯Ό λ§Œμ‘±ν•œλ‹€.

간단 증λͺ…:

μˆ˜ν•™μ μœΌλ‘œ 증λͺ…ν•˜λŠ” 방법이 μžˆμ§€λ§Œ 이해λ₯Ό μœ„ν•΄μ„œ κ°„λ‹¨νžˆ μ„€λͺ…ν•˜μžλ©΄ μ•„λž˜μ™€ 같이 ν‘œν˜„ν•  수 μžˆλ‹€.

b = r x m + n으둜 ν‘œν˜„ν•  λ•Œ, n이 0이라면 b = rm으둜 ν‘œν˜„λœλ‹€. 즉, b와 r의 μ΅œλŒ€ κ³΅μ•½μˆ˜ GCD(b, r) = m이 λœλ‹€.

a = bq + r = rmq + r = r(mq + 1) μ΄λ―€λ‘œ GCD(a, b) = r 이닀.

=> GCD(a, b) = GCD(b, r) = GCD(r, 0) = r

LCM(Lowest Common Multiple) μ΅œλŒ€ κ³΅μ•½μˆ˜ κ΅¬ν•˜κΈ°

def lcm(a, b):
    return a // gcd(a, b) * b

a와 b의 μ΅œλŒ€ κ³΅μ•½μˆ˜ GCD(a, b) = m이라고 ν–ˆμ„ λ•Œ,

a = Am, b = Bm으둜 ν‘œν˜„ ν•  수 μžˆλ‹€.

μ΄λ•Œ, μ΅œλŒ€ κ³΅μ•½μˆ˜(M) = ABm 이닀.

λ”°λΌμ„œ a % m * b = Am % m * Bm = ABm이 λœλ‹€.

728x90
λ°˜μ‘ν˜•