POW1 [백준] 1629번 - 곱셈 문제 풀이 및 코드 해석 (Python) 1. 문제 분석📌 문제 개요A^B mod C를 빠르게 계산하는 문제B가 최대 2,147,483,647이므로 직접 계산하면 시간 초과 발생거듭제곱을 O(log B)로 최적화해야 한다!🎯 요구사항거듭제곱을 빠르게 계산해야 한다.큰 수 연산을 방지하기 위해 매 연산마다 mod C를 적용해야 한다.반복문 또는 재귀를 활용하여 효율적으로 구현해야 한다.2. 해결 방법🔹 핵심 개념분할 정복을 이용한 거듭제곱 (Exponentiation by Squaring)O(B)가 아니라 O(log B)로 거듭제곱을 구하는 방법재귀적으로 B를 절반으로 나누어 계산🔑 해결 절차거듭제곱 분할 정복A^B mod C를 직접 계산하지 않고 재귀적으로 반으로 나눠서 계산B가 짝수일 때와 홀수일 때를 구분하여 처리매 연산마다 mod .. 2025. 3. 7. 이전 1 다음
