복잡도

정수론 알고리즘의 복잡도는 입력 "개수"가 아니라 입력 "값의 크기"로 말하는 경우가 많습니다. 숫자 n 하나를 받는 알고리즘이 O(n)이면, 입력 길이(자릿수 log n)에 대해서는 지수 시간이라는 점을 기억해 두세요. 이 장에서는 각 알고리즘의 시간 · 공간 복잡도를 정리하고 대안과 비교합니다.

유클리드 호제법: O(log min(a, b))

나머지를 두 번 취할 때마다 큰 쪽 값은 적어도 절반 이하로 줄어듭니다. 그래서 반복 횟수는 O(log min(a, b))이고, 확장 버전도 같은 횟수에 상수 배의 일만 더합니다. 가장 느린 입력은 연속한 피보나치 수입니다(라메의 정리). 몫이 매번 1이라서 한 단계에 조금씩만 줄어들기 때문입니다.

def gcd_steps(a: int, b: int) -> int:
    steps = 0
    while b:
        a, b = b, a % b
        steps += 1
    return steps

fib = [1, 1]
while len(fib) < 50:
    fib.append(fib[-1] + fib[-2])

print(gcd_steps(fib[49], fib[48]))  # 48 — 약 1.3 × 10^10 크기의 수인데도 48단계
print(gcd_steps(10**18, 3))         # 2

64비트 범위의 어떤 두 수라도 100단계를 넘지 않습니다. 사실상 상수 시간처럼 다뤄도 됩니다.

빠른 거듭제곱: O(log e)

지수 e의 비트 수만큼 반복하고, 반복마다 곱셈과 나머지 연산을 최대 두 번 합니다. 순진하게 e번 곱하는 방법은 O(e)라서 e = 10^18이면 현실적으로 끝나지 않지만, 빠른 거듭제곱은 약 60번이면 됩니다. 공간은 O(1)입니다. 같은 원리를 행렬에 적용하면 피보나치 수 같은 선형 점화식을 O(k^3 log n)에 구할 수 있습니다.

에라토스테네스의 체: O(n log log n)

소수 p마다 약 n / p개의 칸을 지우므로 전체 작업량은 n × (1/2 + 1/3 + 1/5 + …)이고, 소수의 역수 합은 log log n처럼 자랍니다. n = 10^7이어도 log log n은 3 정도라서 거의 선형입니다. 공간은 O(n)이며, 비트 배열을 쓰면 n / 8바이트까지 줄일 수 있습니다.

각 합성수를 정확히 한 번만 지우는 선형 체(오일러의 체)는 O(n)이고, 덤으로 각 수의 가장 작은 소인수(SPF)를 기록합니다. SPF 표가 있으면 어떤 수든 O(log n)에 소인수분해할 수 있습니다.

def linear_sieve(n: int) -> tuple[list[int], list[int]]:
    spf = [0] * (n + 1)          # spf[k] = k의 가장 작은 소인수
    primes: list[int] = []
    for i in range(2, n + 1):
        if spf[i] == 0:
            spf[i] = i
            primes.append(i)
        for p in primes:
            if p > spf[i] or i * p > n:
                break
            spf[i * p] = p
    return primes, spf

def factorize(k: int, spf: list[int]) -> dict[int, int]:
    factors: dict[int, int] = {}
    while k > 1:
        p = spf[k]
        factors[p] = factors.get(p, 0) + 1
        k //= p
    return factors

primes, spf = linear_sieve(1000)
print(len(primes))          # 168
print(factorize(360, spf))  # {2: 3, 3: 2, 5: 1}

소인수분해: 시행 나눗셈 O(√n)

수 하나만 분해한다면 체를 만들 필요 없이 √n까지 나눠 보면 됩니다. n이 10^12이면 최대 10^6번 나눕니다. 그보다 큰 수(예: 10^18)를 자주 분해해야 한다면 밀러-라빈 소수 판정과 폴라드 로 알고리즘을 함께 쓰는 것이 일반적입니다.

import math

def trial_division(n: int) -> list[int]:
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1 if d == 2 else 2   # 2 다음부터는 홀수만
    if n > 1:
        factors.append(n)
    return factors

print(trial_division(360))            # [2, 2, 2, 3, 3, 5]
print(trial_division(600851475143))   # [71, 839, 1471, 6857]
print(math.isqrt(10**12))             # 1000000 — 반복 상한

nCr mod p: 전처리 O(n), 질의 O(1)

n!과 그 역원 (n!)^(-1)을 n까지 미리 계산해 두면 각 질의는 곱셈 두 번으로 끝납니다. 역팩토리얼은 inv_fact[n] 하나만 페르마로 구하고(O(log p)), 나머지는 inv_fact[k - 1] = inv_fact[k] × k로 거꾸로 채웁니다. 질의가 하나뿐이고 r이 작다면 앞 장처럼 O(r + log p)로 직접 계산하는 편이 간단합니다. n이 p보다 크거나 같으면 팩토리얼이 0이 되므로 뤼카의 정리가 필요합니다.

비교 표

정리

유클리드 호제법과 빠른 거듭제곱은 로그 시간이라 거의 공짜로 쓸 수 있습니다. 소수가 범위 안에서 많이 필요하면 체(O(n log log n))를, 수 하나만 다루면 시행 나눗셈(O(√n))을 고릅니다. 같은 법으로 이항 계수를 여러 번 구한다면 팩토리얼과 역팩토리얼을 미리 만들어 두는 것이 정석입니다. 복잡도를 말할 때는 입력 값의 크기와 자릿수를 구분하는 습관을 들이세요.