빠른 모듈러 거듭제곱
pow(a, b, m)으로 거듭제곱을 계산합니다
빠른 모듈러 거듭제곱은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
거듭제곱 문제
모듈러 아래에서 매우 큰 지수로 수를 거듭제곱해야 하는 경우가 많습니다. 한 번에 한 인수씩 곱하면 단계가 너무 많아집니다. ⚡
단순한 방법은 너무 느립니다
b번 곱하는 반복문은 O(b) 단계가 필요합니다. 지수가 10억에 가까우면 완료되기도 전에 시간 제한을 초과합니다.
for _ in range(b): r = r * a % MOD제곱으로 더 빠르게 올라가기
비결은 제곱하기입니다. a의 8제곱은 ((a의 제곱)의 제곱)의 제곱과 같습니다. 제곱할 때마다 지수가 두 배가 되므로, 몇 단계만에 매우 큰 거듭제곱에 도달할 수 있습니다.
지수를 이진수로 읽기
모든 지수는 2의 거듭제곱들의 합이며, 이것이 지수의 이진 표현입니다. 따라서 비트가 1인 위치의 밑의 거듭제곱만 곱하고 나머지는 건너뛰면 됩니다.
# 13 = 1101 -> a^8 * a^4 * a^1최하위 비트 확인하기
최하위 비트를 확인하려면 b & 1을 보세요. 값이 1이면 다음 단계로 넘어가기 전에 현재 밑을 현재까지의 결과에 곱하세요.
if b & 1: result = result * base % MOD매번 시프트하고 제곱하기
각 비트를 처리한 뒤 밑을 제곱하고 지수를 오른쪽으로 한 비트 시프트하세요. 현실적인 입력이라면 반복 횟수는 약 30~60번에 불과합니다.
base = base * base % MOD
b >>= 1한데 모아 적용하기
결과를 1로 시작한 다음 지수가 양수인 동안 반복하세요. 이 빠른 거듭제곱 방식은 이진 거듭제곱 또는 제곱을 이용한 거듭제곱이라고도 합니다.
result = 1
while b > 0:
if b & 1: result = result*base%MOD
base = base*base%MOD
b >>= 1로그 시간에 실행됩니다
각 단계에서 지수가 절반으로 줄어들기 때문에 비용은 O(log b)입니다. 따라서 10억 번의 곱셈을 대략 30번으로 줄여 어떤 시간 제한 안에서도 충분히 처리할 수 있습니다.
파이썬이 pow를 제공합니다
반복문을 직접 작성하는 경우는 드뭅니다. 파이썬의 내장 pow(a, b, m)가 순수 C 수준의 속도로 빠른 모듈러 거듭제곱을 대신 수행합니다.
print(pow(2, 100, MOD))곧 배울 내용에서 중요한 이유
빠른 거듭제곱은 다음에 배울 페르마의 모듈러 역원을 구하는 핵심 방법입니다. 지금 익혀 두면 모듈러에서의 나눗셈도 쉽게 처리할 수 있습니다.
먼저 밑을 확인하세요
반복문 전에 base % MOD로 밑을 줄이세요. 밑이 이미 모듈러보다 크다면 그렇지 않을 경우 매번 제곱할 때마다 값이 불필요하게 커집니다.
base = a % MOD빠른 모듈러 거듭제곱의 속도
빠른 모듈러 거듭제곱은 얼마나 빠른가요?
요약
이제 제곱하고 비트를 읽어 O(log b) 시간에 매우 큰 지수로 수를 거듭제곱할 수 있습니다. 파이썬에서는 pow(a, b, m)을 호출하면 됩니다. 🚀
자주 묻는 질문
“빠른 모듈러 거듭제곱” 강의는 무료인가요?
네 — “빠른 모듈러 거듭제곱” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“빠른 모듈러 거듭제곱”에서 뭘 배우나요?
pow(a, b, m)으로 거듭제곱을 계산합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“빠른 모듈러 거듭제곱” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.