출시·고도화 중
Algorithm
최대공약수, 모듈러 연산과 역원, 빠른 거듭제곱, 에라토스테네스의 체, nCr mod p까지 알고리즘 문제에 자주 나오는 정수론 도구를 정리합니다.
정수론은 정수의 나눗셈과 나머지를 다루는 수학 분야입니다. 알고리즘에서는 유클리드 호제법으로 최대공약수와 최소공배수를 구하고, 모듈러 연산으로 큰 수를 나머지로 다루며, 확장 유클리드 호제법이나 페르마의 소정리로 모듈러 역원을 구합니다. 여기에 빠른 거듭제곱, 에라토스테네스의 체, 소인수분해, 소수를 법으로 하는 이항 계수 계산이 더해져 하나의 도구 상자를 이룹니다.
이 도구들은 코딩 테스트에서 "10^9 + 7로 나눈 나머지를 출력하라"는 문제로 자주 등장하고, 실무에서는 RSA와 Diffie-Hellman 같은 공개 키 암호, 해시 함수, 난수 생성기, 검증 숫자의 바탕이 됩니다. 대부분 로그 시간이나 거의 선형 시간에 동작하므로, 원리를 알면 순진한 방법으로는 끝나지 않는 계산을 순식간에 처리할 수 있습니다.
먼저 나머지 연산의 성질과 유클리드 호제법을 손으로 추적해 보고, 빠른 거듭제곱과 체를 직접 구현해 보는 것이 좋습니다. 그다음 모듈러 역원과 nCr mod p로 넘어가고, C++이나 Java를 쓴다면 곱셈 오버플로와 음수 나머지 처리를 반드시 연습하세요. Python의 pow(a, e, m)과 math.gcd 같은 표준 기능도 함께 익혀 두면 좋습니다.
gcd(a, b) = gcd(b, a mod b)를 반복해 최대공약수를 O(log n)에 구하고, 확장 버전은 ax + by = gcd(a, b)의 계수까지 함께 구합니다.
덧셈·뺄셈·곱셈은 나머지를 보존하므로 매 단계 나머지를 취해 수를 작게 유지하고, 나눗셈은 모듈러 역원을 곱하는 것으로 바꿉니다.
지수를 이진수로 보고 밑을 제곱해 가며 곱해서, a^e mod m을 e번이 아닌 약 log e번의 곱셈으로 계산합니다.
소수의 배수를 i × i부터 지워 n 이하의 소수를 O(n log log n)에 모두 찾고, 가장 작은 소인수 표로 빠르게 소인수분해합니다.
gcd는 유클리드 호제법으로 최대공약수를 구하고, 최소공배수는 a // gcd(a, b) * b로 얻습니다. mod_pow는 지수의 비트를 하나씩 보며 제곱과 곱셈을 반복하는 빠른 거듭제곱이고, 소수 법에서 a^(p-2)를 계산하면 a의 모듈러 역원이 됩니다. sieve는 에라토스테네스의 체로 30 이하의 소수를 모두 찾습니다. 파일로 저장해 python number_theory.py로 실행하세요.
number_theory.py
import math
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
def mod_pow(base: int, exp: int, mod: int) -> int:
result, base = 1 % mod, base % mod
while exp > 0:
if exp & 1:
result = result * base % mod
base = base * base % mod
exp >>= 1
return result
def sieve(n: int) -> list[int]:
is_prime = [False, False] + [True] * (n - 1)
for i in range(2, math.isqrt(n) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return [i for i, p in enumerate(is_prime) if p]
MOD = 10**9 + 7
print(gcd(84, 36), 84 // gcd(84, 36) * 36) # 12 252
print(mod_pow(3, 200, 13)) # 9
print(mod_pow(3, MOD - 2, MOD)) # 333333336, the inverse of 3
print(sieve(30)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
python number_theory.py수학과 정수론 에 관해 묻고, 경험을 나누고, 의견을 주고받는 곳입니다.
아직 토론이 없습니다. 첫 이야기를 시작해 보세요.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.
첫 댓글을 남겨 보세요.