나머지 연산

나머지 연산이란?

a % b는 a를 b로 나눈 나머지입니다. 단순해 보이지만, "주기", "홀짝", "큰 수
다루기" 등 수많은 문제의 핵심 도구입니다.

1. 기본 의미

cout << 17 % 5 << '\n';   // 2  (17 = 5*3 + 2)
cout << 10 % 2 << '\n';   // 0  (나누어 떨어짐)

a % b의 결과는 항상 \(0\) 이상 \(b\) 미만입니다(양수 기준). 그래서 0부터 b-1까지의
값으로 분류하는 데 자연스럽게 쓰입니다.

2. 가장 흔한 쓰임 3가지

(1) 홀짝 판정

if (n % 2 == 0) cout << "짝수";
else            cout << "홀수";

(2) 배수 판정 — "k의 배수인가?"는 n % k == 0.

(3) 순환(주기) — 시계처럼 일정 주기로 돌아오는 값.

int hour = (now + add) % 24;   // 24시간이 지나면 0으로

3. 나머지 연산의 성질

큰 수를 다룰 때 핵심이 되는 성질입니다. 나머지는 더하기·곱하기 전에 미리 취해도
결과가 같습니다.

$$ (a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m $$
$$ (a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m $$

덕분에 "답을 1,000,000,007로 나눈 나머지를 출력" 같은 문제에서 중간중간 나머지를
취해 수가 커지는 것을 막을 수 있습니다.

const int MOD = 1000000007;
long long ans = 1;
for (int i = 1; i <= n; i++)
    ans = ans * i % MOD;   // 매번 나머지 -> 오버플로 방지

4. 음수 나머지 주의

C++에서 -7 % 3은 -1이 나옵니다(음수!). "항상 0 이상"으로 만들려면:

int r = ((x % m) + m) % m;   // 0 이상 m 미만 보장

파이썬의 %는 항상 0 이상이라 이 보정이 필요 없습니다.

복잡도

나머지 연산은 \(O(1)\)입니다. 다만 큰 수 문제에서 "언제 나머지를 취할지"의 설계가
중요합니다.

정리

• a % b는 \(0\) 이상 \(b\) 미만(양수).
• 홀짝·배수·주기 처리의 기본 도구.
• 더하기·곱하기 전에 나머지를 취해도 결과가 같다 — 오버플로 방지.
• C++의 음수 나머지는 음수가 될 수 있다.

나머지 연산 구현 레퍼런스

나머지 연산이 실제 문제에서 어떻게 쓰이는지, 특히 큰 수의 나머지와 주기
패턴을 코드로 정리합니다.

1. 큰 수의 거듭제곱 나머지

\(a^n \bmod m\)을 곧이곧대로 pow로 구하면 수가 폭발합니다. 곱할 때마다 나머지를
취하세요.

const long long MOD = 1000000007;
long long result = 1;
for (int i = 0; i < n; i++)
    result = result * a % MOD;   // 매 단계 나머지
cout << result << '\n';

MOD = 1000000007
result = 1
for _ in range(n):
    result = result * a % MOD
print(result)
# 참고: 파이썬은 pow(a, n, MOD) 한 줄로도 가능

result는 반드시 long long이어야 합니다. MOD가 약 \(10^9\)라 곱하면 \(10^{18}\)에
가까워져 int는 넘칩니다.

2. 자릿수의 합으로 배수 판정

"각 자리 숫자의 합이 3의 배수면 그 수는 3의 배수"라는 성질을 활용:

int n; cin >> n;
int digitSum = 0;
while (n > 0) {
    digitSum += n % 10;   // 맨 끝 자리
    n /= 10;              // 끝 자리 버리기
}
cout << (digitSum % 3 == 0 ? "배수" : "아님") << '\n';

n = int(input())
digit_sum = sum(int(c) for c in str(n))
print("배수" if digit_sum % 3 == 0 else "아님")

% 10(끝 자리)과 / 10(끝 자리 제거)의 조합은 자릿수 처리의 정석입니다.

3. 주기 문제

// 0,1,2,3,0,1,2,3,... 처럼 4 주기로 도는 값
for (int i = 0; i < n; i++)
    cout << i % 4 << ' ';

"며칠 후 무슨 요일?", "회전 후 위치" 같은 문제는 % 주기로 깔끔히 풀립니다.

4. 함정과 패턴 인식

• 오버플로 — 나머지를 취하기 전에 곱셈 결과가 이미 넘침. 곱은 long long.
• 음수 나머지 — C++에서 입력이 음수면 결과가 음수. ((x%m)+m)%m로 보정.
• 나머지 깜빡 — 큰 수 문제에서 마지막에만 나머지 취하면 이미 늦음. 중간마다.

문제에 "~로 나눈 나머지를 출력", "홀수/짝수", "k의 배수", "주기적으로 반복"
같은 말이 보이면 나머지 연산이 열쇠입니다.

정리

나머지 연산의 실전 핵심은 (1) 곱셈 전 long long, (2) 매 단계 나머지로 오버플로
차단, (3) 자릿수 분리(%10, /10), (4) 주기는 % 주기 — 이 네 가지입니다.