전처리 (Precomputation)

2026년 6월 25일 · 수정 2026년 6월 25일 · 📖 약 4분 · 1,164자/단어 #algorithm #query #precomputation

정의

전처리 (Precomputation) 는 런타임 이전 또는 초기화 단계에서 필요한 값을 미리 계산해 두고, 본 쿼리/연산을 빠르게 처리하는 정형. 대표적으로 테이블 채우기, 캐시 구축, 메모이제이션(memoization) 이 있다.

prefix sum, sieve, factorial/modular inverse 테이블, sparse table 등 사실상 모든 효율적인 알고리즘이 어떤 형태로든 전처리를 사용한다.

문제 상황과 동기

동일한 입력 조합이 여러 번 등장하거나, 쿼리(Q)가 매우 많아서 매번 O(N) 연산이 불가능할 때 전처리가 필요하다.

naive: 매 쿼리마다 원시 연산. O(NQ).
전처리: O(P) 한 번만 계산 후 O(1) 또는 O(log N) 쿼리. 총 O(P + Q).

N = Q = 10^5, naive O(NQ) = 10^10. 전처리로 O(N + Q) = 2 x 10^5 로 떨어진다.

핵심 통찰: “한 번 계산한 결과를 저장하고 재사용한다” 는 시간-공간 trade-off 의 정수.

시각화

핵심 아이디어

invariant: 전처리 테이블 T[i] 는 i 에 대한 답을 담고 있으며, 이후 모든 쿼리는 T 에서 O(1) 조회한다.

// 일반적인 전처리 패턴
precompute(input):
    T = array of size N+1
    for i in 1..N:
        T[i] = f(T[i-1], input[i])   // 점화식

query(l, r):
    return combine(T[r], T[l-1])      // O(1)

전처리는 다음과 같은 형태로 분류된다:

형태	예시
누적 테이블	구간 합 O(1)
희소 테이블	구간 최소/최대 O(1)
팩토리얼 / 조합	nCr O(1)
소수 판별	체 + O(log N) 소인수분해
메모이제이션	DP O(N)

알고리즘

팩토리얼 + 역원 전처리 (mod nCr)

precompute_fact(N, MOD):
    fact[0] = 1
    for i in 1..N:
        fact[i] = fact[i-1] * i % MOD
    inv_fact[N] = pow(fact[N], MOD-2, MOD)  // Fermat
    for i in N-1..0:
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

nCr(n, r):
    if r < 0 or r > n: return 0
    return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD

구현

// 팩토리얼 + 조합 전처리, O(N) pre + O(1) query
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
const int MAX = 1000000;

ll fact[MAX+1], inv_fact[MAX+1];

ll mod_pow(ll a, ll e) {
  ll r = 1;
  while (e) {
      if (e & 1) r = r * a % MOD;
      a = a * a % MOD;
      e >>= 1;
  }
  return r;
}

void precompute() {
  fact[0] = 1;
  for (int i = 1; i <= MAX; i++)
      fact[i] = fact[i-1] * i % MOD;
  inv_fact[MAX] = mod_pow(fact[MAX], MOD-2);
  for (int i = MAX-1; i >= 0; i--)
      inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

ll nCr(int n, int r) {
  if (r < 0 || r > n) return 0;
  return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}

int main() {
  precompute();
  int q; cin >> q;
  while (q--) {
      int n, r; cin >> n >> r;
      cout << nCr(n, r) << "\n";
  }
}

# 팩토리얼 + 조합 전처리, O(N) pre + O(1) query
MOD = 10**9+7
MAX = 1000000

fact = [1] * (MAX + 1)
inv_fact = [1] * (MAX + 1)

for i in range(1, MAX + 1):
  fact[i] = fact[i-1] * i % MOD

inv_fact[MAX] = pow(fact[MAX], MOD-2, MOD)
for i in range(MAX-1, -1, -1):
  inv_fact[i] = inv_fact[i+1] * (i+1) % MOD

def nCr(n, r):
  if r < 0 or r > n: return 0
  return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD

import sys
input = sys.stdin.readline
q = int(input())
out = []
for _ in range(q):
  n, r = map(int, input().split())
  out.append(str(nCr(n, r)))
print("\n".join(out))

// 팩토리얼 + 조합 전처리, O(N) pre + O(1) query
import java.util.*;
import java.io.*;
public class Main {
  static final long MOD = 1_000_000_007L;
  static final int MAX = 1_000_000;
  static long[] fact = new long[MAX+1];
  static long[] invFact = new long[MAX+1];

  static long modPow(long a, long e) {
      long r = 1;
      while (e > 0) {
          if ((e & 1) == 1) r = r * a % MOD;
          a = a * a % MOD;
          e >>= 1;
      }
      return r;
  }

  static void precompute() {
      fact[0] = 1;
      for (int i = 1; i <= MAX; i++)
          fact[i] = fact[i-1] * i % MOD;
      invFact[MAX] = modPow(fact[MAX], MOD-2);
      for (int i = MAX-1; i >= 0; i--)
          invFact[i] = invFact[i+1] * (i+1) % MOD;
  }

  static long nCr(int n, int r) {
      if (r < 0 || r > n) return 0;
      return fact[n] * invFact[r] % MOD * invFact[n-r] % MOD;
  }

  public static void main(String[] args) throws IOException {
      precompute();
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int q = Integer.parseInt(br.readLine().trim());
      StringBuilder sb = new StringBuilder();
      while (q-- > 0) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int n = Integer.parseInt(st.nextToken());
          int r = Integer.parseInt(st.nextToken());
          sb.append(nCr(n, r)).append('\n');
      }
      System.out.print(sb);
  }
}

stdin

결과

복잡도

항목	값
전처리 시간	O(N) 또는 O(N log N)
쿼리 시간	O(1) 또는 O(log N)
공간	O(N)
장점	Q 가 클수록 압도적 이득
단점	N 이 매우 크면 공간 초과 가능

변형 / 활용

종류	설명
[[Prefix Sum	누적 합]]
[[Sparse Table	희소 배열]]
[[Segtree	세그먼트 트리]]
[[Sieve	에라토스테네스의 체]]
[[DP	동적 계획법]]

함정

1. 공간 초과

N=10^6 sparse table = 20 x 8 x 10^6 = 160 MB. 메모리 제한 확인 필수.

2. 부분 갱신

전처리 테이블은 보통 immutable. 원본 변경 시 재계산 필요. 갱신이 잦다면 세그먼트 트리나 펜윅 트리 고려.

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 11659	구간 합 구하기 4	-	kokoa-lab
BOJ 11401	이항 계수 3	-	kokoa-lab
BOJ 1016	제곱 ㄴㄴ 수	-	kokoa-lab
BOJ 13977	이항 계수와 쿼리	-	kokoa-lab
BOJ 17435	합성함수와 쿼리	-	kokoa-lab

참고

이 글의 용어 (7개)

누적 합 (Prefix Sum)algorithm: 정의 누적 합 (Prefix Sum) 은 배열 에 대해 (또는 1-indexed ) 을 미리 계산해 두고, 임의 구간 합 을 O(1) 에 구하는 정형. 문제 풀이에서 "구간 N …
동적 계획법 (Dynamic Programming)algorithm: 정의 동적 계획법 (Dynamic Programming, DP) 은 큰 문제를 작은 부분 문제로 나누고, 각 부분 문제의 최적해를 저장하여 중복 계산을 제거하는 최적화 기법. R…
세그먼트 트리 (Segment Tree)algorithm: 정의 세그먼트 트리 (Segment Tree) 는 배열의 구간 쿼리 (range query) 와 점 갱신 (point update) 를 모두 O(log N) 에 처리하는 이진 트…
에라토스테네스의 체 (Sieve of Eratosthenes)algorithm: 정의 에라토스테네스의 체 (Sieve of Eratosthenes) 는 1부터 N 까지의 모든 소수를 O(N log log N) 에 찾는 고대 그리스 알고리즘. 기원전 240 년…
희소 배열 (Sparse Table)algorithm: 정의 희소 배열 (Sparse Table) 은 정적 배열에서 결합 법칙을 만족하는 idempotent 연산 (min, max, gcd, lcm 등) 의 구간 쿼리를 O(1) 시간…
Fenwick Tree (Binary Indexed Tree): 구간 합 O(log N)algorithm: 정의 Fenwick Tree (또는 BIT, Binary Indexed Tree) 는 배열의 prefix sum 을 O(log N) 에 갱신·조회 하는 자료구조입니다. Peter…
Offline Queries (오프라인 쿼리)algorithm: 정의 오프라인 쿼리 (Offline Queries) 는 쿼리가 주어진 순서대로 처리하지 않고, 효율성을 위해 재정렬하거나 배치 처리 하는 기법. 쿼리를 다시 정렬하여 정렬 상태를…