본문으로 건너뛰기
series develop frontend backend cs algorithm numbertheory modular bigint

정수를 다루는 도구들 - 이름과 비용: 알고리즘 ep.06

정수론은 별도의 주제로 등장하기보다 다른 문제를 풀다가 중간에 필요해집니다.

나머지를 반복해 최대공약수를 찾습니다

두 수의 최대공약수(greatest common divisor) 를 구할 때 약수를 나열해 비교할 이유가 없습니다.

유클리드 호제법(Euclidean algorithm) 은 a와 b의 최대공약수가 b와 a를 b로 나눈 나머지의 최대공약수와 같다는 성질을 씁니다. 나머지는 b보다 작으므로 반복하면 빠르게 줄어들고, 나머지가 0이 되는 순간의 값이 답입니다.

유클리드 호제법으로 48과 18의 최대공약수를 구하는 과정을 세 단계로 보여주는 다이어그램. 각 줄에 두 수와 나머지 칸이 있고 나누는 수가 초록으로 표시됨. 1회는 48과 18에서 나머지 12이고 「48 = 18 × 2 + 12」, 2회는 18과 12에서 나머지 6이고 「18 = 12 × 1 + 6」, 3회는 12와 6에서 나머지 0이고 「12 = 6 × 2 + 0」이며 마지막 나머지 칸은 주황으로 표시됨. 각 줄에서 다음 줄로 값이 옮겨가는 화살표가 있음. 아래에 「나머지가 0이 되는 순간의 나눈 수 6이 최대공약수입니다」라고 적혀 있음. 다이어그램 제목은 「나머지로 바꿔가며 줄이면 금방 끝납니다」, 부제는 「48과 18의 최대공약수 · a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같습니다」이고 하단에 「두 단계마다 값이 최소 절반 이하로 떨어지므로 반복 횟수가 O(log(min(a, b)))입니다. 48과 18은 세 번 만에 끝났습니다」, 「약수를 나열해 비교하면 48의 약수 10개와 18의 약수 6개를 모두 구해야 합니다」라고 적혀 있음.

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

줄어드는 속도가 빠릅니다. 두 단계마다 값이 최소 절반 이하로 떨어져 O(log(min(a, b)))입니다.

최소공배수(least common multiple) 는 두 수의 곱을 최대공약수로 나누면 바로 나옵니다.

function lcm(a, b) {
  return (a / gcd(a, b)) * b; // 먼저 나눠서 중간값이 커지는 것을 막는다
}

곱한 뒤 나누지 않고 먼저 나누는 이유는 a * b가 안전한 정수 범위를 넘으면 값이 틀어지기 때문입니다. 이 문제는 아래에서 다시 봅니다.

화면 비율을 줄일 때 이 계산을 씁니다. 1920과 1080의 최대공약수가 120이므로 양쪽을 나누면 16 대 9가 나옵니다. 서로 다른 주기로 도는 작업 두 개가 언제 다시 겹치는지 알아야 할 때는 최소공배수를 씁니다.

배수를 지워 소수만 남깁니다

특정 수 하나가 소수인지 확인하는 건 제곱근까지만 나눠보면 됩니다. N보다 작은 모든 소수를 구해야 한다면 이 방법을 N번 반복하는 대신 다른 접근이 낫습니다.

에라토스테네스의 체(sieve of Eratosthenes) 는 남은 수 중 가장 작은 것을 소수로 확정하고 그 배수를 전부 지웁니다.

에라토스테네스의 체가 동작하는 과정을 4단계로 보여주는 다이어그램. 2부터 30까지의 숫자가 격자 형태로 배열되어 있음. 1단계에서 2가 소수로 확정되어 진한 색으로 표시되고 4, 6, 8부터 30까지 2의 배수가 회색으로 지워짐. 2단계에서 남은 가장 작은 수 3이 소수로 확정되고 9, 15, 21, 27이 지워짐. 6, 12 같은 수는 이미 지워진 상태로 표시됨. 3단계에서 5가 확정되고 25가 지워짐. 4단계에서 7이 확정되지만 49가 30을 넘으므로 지울 대상이 없고, 이 시점에 남은 수가 모두 소수임이 표시됨. 격자 아래에 각 소수 p의 배수를 지울 때 p 곱하기 p부터 시작하면 되는 이유가 그 앞의 배수는 더 작은 소수가 이미 지웠기 때문이라는 설명으로 적혀 있음. 다이어그램 제목은 「지울 수를 세는 것이 아니라, 남는 수를 세는 방법」, 부제는 「2부터 30까지 · 남은 가장 작은 수가 곧 다음 소수입니다」임. 각 단계 머리글은 「STEP 1 · 2를 확정하고 2의 배수를 지웁니다」(4부터 시작, 2×2), 「STEP 2 · 남은 가장 작은 수 3을 확정합니다」(9부터 시작, 6은 2가 이미 지움), 「STEP 3 · 5를 확정합니다」(25부터 시작, 10·15·20은 이미 지워짐), 「STEP 4 · 7 이후로는 지울 것이 없습니다」(7×7 = 49는 30을 넘으므로 남은 수가 전부 소수)임. 하단 상자 「왜 p × p부터 지워도 되는가」에는 p × p가 범위를 넘으면 그 뒤로는 지울 것이 없고 이것이 바깥 반복을 √N에서 멈추는 근거라는 설명과, 전체 비용은 O(N log log N)이며 소수 하나를 판정하는 것과 범위 전체를 거르는 것은 다른 문제라는 문장이 함께 적혀 있음.

function sieve(n) {
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let p = 2; p * p <= n; p++) {
    if (!isPrime[p]) continue;
    // p보다 작은 배수는 더 작은 소수가 이미 지웠다
    for (let multiple = p * p; multiple <= n; multiple += p) {
      isPrime[multiple] = false;
    }
  }

  const primes = [];
  for (let i = 2; i <= n; i++) if (isPrime[i]) primes.push(i);
  return primes;
}

두 가지 최적화가 들어 있습니다. 바깥 반복문이 제곱근까지만 도는 이유는, N 이하의 합성수라면 제곱근 이하의 약수를 반드시 갖기 때문입니다. 안쪽에서 p * p부터 시작하는 이유는 그보다 작은 배수는 더 작은 소수가 처리했기 때문입니다.

전체 복잡도는 O(N log log N)입니다. N이 백만이어도 log log N은 한 자리 수라 수백만 번 안팎으로, 사실상 선형에 가깝습니다.

미리 구해둔 소수 목록은 해시 테이블의 버킷 수를 정할 때 씁니다. 버킷 수를 소수로 두면 키가 특정 간격으로 몰려 있어도 나머지가 고르게 퍼집니다.

나머지는 계산 도중에 취해도 됩니다

큰 수를 다루는 문제에서 답을 특정 값으로 나눈 나머지로 요구하는 경우가 흔합니다. 최종 결과를 계산한 뒤 나누는 것이 아니라 계산 도중에 계속 나머지를 취해야 합니다. 그렇게 해도 되는 근거가 모듈러 연산(modular arithmetic) 의 성질입니다.

덧셈, 뺄셈, 곱셈은 중간에 나머지를 취해도 결과가 같습니다.

  • (a + b) % m === ((a % m) + (b % m)) % m
  • (a * b) % m === ((a % m) * (b % m)) % m

곱셈에서 중간에 나머지를 취해도 결과가 같다는 것을 두 패널로 비교한 다이어그램. 왼쪽 「끝까지 곱한 뒤 나누기」 패널에는 「123 × 456 = 56,088」과 「56,088 % 7 = 3」이 적혀 있고 「중간값이 커집니다. 수가 커지면 안전한 정수 범위를 넘습니다」라고 덧붙어 있음. 오른쪽 「먼저 나머지를 취하고 곱하기」 패널에는 「123 % 7 = 4 · 456 % 7 = 1」과 「(4 × 1) % 7 = 3」이 적혀 있고 「중간값이 작게 유지됩니다. 결과는 위와 같은 3입니다」라고 덧붙어 있음. 다이어그램 제목은 「중간에 나머지를 취해도 답이 같습니다」, 부제는 「123 × 456을 7로 나눈 나머지 · 덧셈, 뺄셈, 곱셈에서 성립합니다」이고 하단에 「덧셈과 뺄셈, 곱셈은 이렇게 분배됩니다. 나눗셈은 성립하지 않아 모듈러 곱셈 역원이라는 별도의 개념이 필요합니다」, 「뺄셈은 결과가 음수가 될 수 있어 한 번 더 처리합니다. 자바스크립트의 나머지 연산자는 음수에 음수를 돌려줍니다」, 「그래서 큰 수를 다루는 문제는 계산 도중에 계속 나머지를 취해도 답이 달라지지 않습니다」라고 적혀 있음.

나눗셈은 성립하지 않습니다. (a / b) % m을 그대로 쪼갤 수 없습니다. 모듈러 곱셈 역원이라는 별도의 개념이 필요합니다.

뺄셈에는 주의점이 하나 더 있습니다. 자바스크립트의 %는 음수에 대해 음수를 반환합니다. 나머지를 항상 양수로 유지하려면 한 번 더 처리해야 합니다.

const MOD = 1_000_000_007;

function subMod(a, b) {
  return ((a - b) % MOD + MOD) % MOD; // 음수 방지
}

나머지 연산은 큰 수를 다루는 문제 밖에서도 자주 씁니다. 데이터를 여러 서버에 나눌 때 키의 해시를 서버 수로 나눈 나머지로 목적지를 정하고, 순환 버퍼는 인덱스를 크기로 나눈 나머지로 자리를 찾습니다.

정밀도가 깨지는 경계

자바스크립트의 Number는 배정밀도 부동소수점입니다. 정수를 정확히 표현할 수 있는 범위가 Number.MAX_SAFE_INTEGER, 즉 2의 53승에서 1을 뺀 값까지입니다.

이 범위를 넘으면 오류 없이 조용히 틀린 값이 나옵니다.

Number.MAX_SAFE_INTEGER;        // 9007199254740991
Number.MAX_SAFE_INTEGER + 1;    // 9007199254740992
Number.MAX_SAFE_INTEGER + 2;    // 9007199254740992  (같은 값)

앞에서 최소공배수를 구할 때 먼저 나눈 이유가 여기에 있습니다. 두 수가 각각 10의 9승 정도만 되어도 곱하면 안전 범위를 넘어갑니다.

넘어갈 가능성이 있으면 BigInt를 써야 합니다.

const big = 9007199254740993n;   // 접미사 n
big + 2n;                        // 9007199254740995n

BigInt는 임의 정밀도라 자릿수 제한이 없습니다. 대신 일반 숫자와 직접 섞어 연산할 수 없고, 연산 속도도 느립니다. 계산 규모를 먼저 어림해보고 필요할 때만 쓰는 것이 맞습니다.

분산 시스템에서 만든 64비트 ID가 이 경계에 걸립니다. 서버가 내려준 ID를 자바스크립트에서 숫자로 받으면 끝자리가 달라질 수 있으므로, 문자열이나 BigInt로 받아야 합니다.

여기서도 판단 순서는 자료구조 시리즈 ep.01 크기가 접근법을 정한다와 같습니다. 값의 범위를 먼저 계산하고, 그 결과로 도구를 정합니다.

두 시리즈를 마치며

「이름과 비용」은 이미 쓰고 있는 것들을 다시 확인하는 작업이었습니다.

자료구조 시리즈에서는 데이터를 담는 구조가 어떤 연산을 싸게 만들고 어떤 연산을 비싸게 만드는지 봤습니다. 배열의 연속성, 해시의 계산된 위치, 트리의 높이, 전처리와 갱신의 거래가 그 내용이었습니다.

알고리즘 시리즈에서는 그 위에서 무엇을 어떻게 찾을지 다뤘습니다. 완전탐색을 기준선에 두고, 구조와 단조성과 국소 최적과 재사용이라는 네 가지 근거로 탐색 공간을 줄이는 방법들을 정리했습니다.

전체를 관통하는 질문은 이 선택의 대가가 무엇인가였습니다. 자료구조를 고르는 일도, 알고리즘을 고르는 일도 결국 무엇을 싸게 만들고 무엇을 비싸게 둘 것인지를 정하는 일입니다.

이름을 알면 찾아볼 수 있고, 비용을 알면 고를 수 있습니다.

참고 자료