Table of Contents

코테에서 분수 나누기 나머지 연산, 이렇게 해결했어요 (feat. 페르마의 소정리)

코딩테스트 준비하다 보면 꼭 이런 조건이 붙은 문제를 만나게 되더라고요.

“정답을 1,000,000,007로 나눈 나머지를 출력하시오.”

처음엔 저도 이게 뭔가 싶었어요. “그냥 계산하고 마지막에 % 1000000007 하면 되는 거 아닌가?” 라고 생각했는데, 조합(nCr) 문제에서 분수가 등장하는 순간 완전히 막혀버렸어요.

더하기, 빼기, 곱하기는 분배법칙으로 나머지 연산이 잘 됐는데, 나누기는 얘기가 달랐어요. 오늘은 그 문제를 어떻게 해결했는지 비전공자 시점에서 최대한 쉽게 풀어볼게요.

나머지 연산이 뭔지부터 짚고 가요

파이썬에서 나머지 연산은 % 기호를 써요. 이걸 모듈로 연산(Modulo Operation) 이라고 부르더라고요.

7 % 3   # 결과: 1 (7을 3으로 나눴을 때 나머지)
10 % 4  # 결과: 2

코딩테스트에서 나머지 연산을 쓰는 이유는 단순해요. 문제의 답이 수억, 수조 단위로 엄청나게 커질 수 있는데, 그 큰 숫자 자체보다는 특정 수로 나눈 나머지만 구하라는 거예요.

컴퓨터 메모리에는 한계가 있고, 너무 큰 숫자는 오버플로우(숫자가 저장 범위를 넘어 오류가 나는 것)가 생길 수 있거든요. 파이썬은 다른 언어보다 이 부분이 관대하긴 한데, 그래도 연산 속도 때문에 나머지를 취해가면서 계산하는 게 훨씬 효율적이에요.

→ % 연산자는 나머지를 구하는 기호, 코테에선 숫자가 커지는 걸 방지하려고 자주 씁니다.

더하기, 빼기, 곱하기는 분배법칙이 돼요

나머지 연산의 가장 편한 점은, 더하기·빼기·곱하기에서는 중간중간 나머지를 취해도 최종 결과가 같다는 거예요.

M = 1000000007

# 더하기
(A + B) % M == ((A % M) + (B % M)) % M  # 성립

# 곱하기
(A * B) % M == ((A % M) * (B % M)) % M  # 성립

이게 왜 중요하냐면, 숫자가 커지기 전에 미리 나머지를 취할 수 있다는 뜻이거든요. 조합 계산처럼 팩토리얼이 엄청나게 커지는 상황에서, 곱할 때마다 % M을 해주면 숫자가 항상 일정 범위 안에 머물러요.

근데 문제는 나누기예요. 나누기는 이 분배법칙이 그냥 성립하지 않아요.

# 이렇게 하면 안 돼요!
(A / B) % M  # 소수점 오차 발생 가능
((A % M) / (B % M)) % M  # 이것도 틀려요

→ 더하기·빼기·곱하기는 분배법칙으로 나머지 처리가 되지만, 나누기는 다른 방법이 필요해요.

나누기를 그냥 하면 왜 안 될까요?

실제로 코테 문제에서 nCr, 즉 조합을 구하는 경우가 많아요. 예를 들어 5C2 = 10 이런 식으로요.

조합 공식은 이렇게 생겼어요.

nCr = n! / (r! * (n-r)!)

여기서 팩토리얼(!)은 1부터 해당 숫자까지 전부 곱한 값이에요. n이 1000만 넘어가도 숫자가 천문학적으로 커져요. 이 상황에서 그냥 나누기를 하면 두 가지 문제가 생겨요.

첫째, 소수점 오차. 파이썬의 / 연산은 부동소수점 나눗셈이에요. 이론상 딱 나눠지는 값도 컴퓨터 내부에서 0.9999… 같이 미세하게 틀릴 수 있어요.

둘째, 나머지 연산과 안 맞음. (A / B) % M 이 방식은 수학적으로 올바른 “모듈러 나눗셈”이 아니에요. 중간에 나머지를 취하고 나서 나눗셈을 하면 결과가 달라지거든요.

솔직히 처음에 이게 왜 문제인지 감이 잘 안 왔는데, 실제로 틀린 답이 나오는 걸 보고 나서야 “아, 진짜 다른 방법이 필요하구나” 싶었어요.

→ 큰 수의 나눗셈을 그냥 하면 오차와 오류가 생기기 때문에 다른 접근이 필요해요.

페르마의 소정리로 나누기를 곱하기로 바꿔요

여기서 등장하는 게 페르마의 소정리(Fermat’s Little Theorem) 예요. 이름이 굉장히 무섭게 생겼는데, 코테에서 쓰는 핵심만 보면 생각보다 간단해요.

수학적 증명은 몰라도 괜찮아요. 저도 몰라요. 중요한 건 이 공식이 성립한다는 것과 어떻게 쓰는지예요.

M이 소수(prime)일 때,
A ÷ B를 M으로 나눈 나머지 = A × B^(M-2)를 M으로 나눈 나머지

말로 풀면, “B로 나누는 것”을 “B의 (M-2)제곱을 곱하는 것”으로 바꿀 수 있다는 거예요. 나누기를 곱하기로 변환하는 거죠.

여기서 B^(M-2)를 모듈러 역원(Modular Inverse) 이라고 불러요. B의 나머지 연산 세계에서의 역수 같은 개념이에요.

코테에서 자주 쓰는 M = 1000000007은 소수예요. 그래서 이 정리를 바로 쓸 수 있어요.

→ 페르마의 소정리 덕분에 나누기를 곱하기로 바꿔서 나머지 연산을 안전하게 할 수 있어요.

파이썬 코드로 바로 써먹는 법

파이썬에는 이걸 한 줄로 처리할 수 있는 내장 기능이 있어요. pow() 함수인데, 세 번째 인자로 M을 넘겨주면 모듈러 지수 연산을 알아서 빠르게 계산해줘요.

M = 1000000007

# A / B % M 을 이렇게 바꿔요
result = A * pow(B, M - 2, M) % M

pow(B, M-2, M) 이 부분이 핵심이에요. B의 (M-2)제곱을 M으로 나눈 나머지를 구해줘요. 이게 나누기 B를 대신하는 값이에요.

실제로 조합 문제에 적용하면 이렇게 돼요.

M = 1000000007

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result = result * i % M  # 중간중간 나머지 취하기
    return result

def combination(n, r):
    # nCr = n! / (r! * (n-r)!)
    numerator = factorial(n)                           # 분자
    denominator = factorial(r) * factorial(n - r) % M  # 분모
    return numerator * pow(denominator, M - 2, M) % M  # 나누기 → 곱하기로 변환

처음에 pow() 세 번째 인자를 몰라서 직접 거듭제곱 계산을 했는데, 그렇게 하면 엄청나게 느려요. pow(B, M-2, M) 이 형태가 내부적으로 훨씬 최적화돼 있으니까 이걸 쓰는 게 맞아요.

→ A * pow(B, M-2, M) % M 이 한 줄이 코테 나누기 나머지 처리의 핵심 공식이에요.

정리하면서

코테 공부하면서 수학적인 개념이 나오면 솔직히 좀 겁부터 났어요. 근데 막상 써보면 “이 공식이 왜 성립하는가”보다 “언제 쓰고 어떻게 쓰는가”만 알아도 문제 푸는 데 충분하더라고요.

페르마의 소정리도 마찬가지예요.

M이 소수일 때 쓸 수 있다
나누기 B를 pow(B, M-2, M) 곱하기로 바꾼다
1000000007은 소수니까 바로 적용 가능하다

이 세 가지만 기억해도 조합 계산이 나오는 코테 문제에서 바로 써먹을 수 있어요. 여러분도 오늘 한 번만 직접 짜보면 손에 바로 익을 거예요.

파이썬 모듈로 연산으로 분수 나누기 정복하기 (페르마의 소정리)