➊ 서론
시간복잡도를 고려하지 않는다면 문제는 굉장히 쉽다.
⬇️ 문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
그러나 A, B, C는 모두 2,147,483,647 이하의 자연수라는 범위 설정 때문에 단순히 곱한다면 수가 굉장히 커지므로 시간 초과가 발생한다.
⬇️ 처음 제출한 코드 (시간 초과)
A, B, C = map(int, input().split())
result = 1
for _ in range(B):
result *= A
print(result % C)그렇다면 이 문제는 어떻게 풀어야 할까?
이 문제를 풀기 위해서는 수학적 지식과 분할 정복에 대한 알고리즘 지식이 필요하다.
➋ 문제 접근 아이디어
① 수학적 아이디어
먼저 지수 법칙과 나머지 연산 분배 법칙에 대한 지식이 필요하다.
지수 법칙은 중고등학교 수학 시간에 배웠던 경험이 있지만,
나머지 연산 분배 법칙은 처음 들어봤기에 이를 이해하는 과정이 필요했다.
왜 (A×B)%C ➡️ (A%C) × (B%C) % C 로 도출되는지 증명을 통해 논리적으로 설명하도록 하겠다.
(A×B)%C의 식에서 A와 B는 다음과 같이 정의할 수 있다.
이때, q는 몫이고 r은 나머지를 의미한다.
이를 좌항에 대입하고 식을 전개하면 다음과 같다.
이때 q1×q2×C^2, q1×C×r2, q2×C×r1 은 C로 나누었을 때 나머지가 0이므로 r1×r2에 대해서만 고려하면 된다!
여기서 r1과 r2의 의미에 대해 다시 생각해보자.
r1은 A를 C로 나누었을 때의 나머지이므로 r1 = A%C 이다.
마찬가지로 r2 = B%C 이다.
즉, 다음과 같이 식을 전개할 수 있다.
따라서 처음 증명하고자 했던 식의 우항과 같으므로
(A×B)%C = (A%C) × (B%C) % C 이 성립한다는 것을 알았다.
나머지 연산 분배 법칙은 덧셈과 뺄셈에 대해서도 성립한다.
증명 과정은 위와 아주 유사하다!
② 분할 정복
이제 이러한 수학적 아이디어를 바탕으로 우리가 풀고자 했던 곱셈 문제에 접근해보자.
A를 B번 곱하고 C로 나눈다고 하였으니
A^B % C 라는 식으로 나타낼 수 있다.
A = 10, B = 11, C = 12를 대입하면 다음과 같다.
10^11 % 12
이때 10^11는 너무 큰 수이기 때문에 나머지 분배 법칙을 이용하여 다음과 같이 쪼갤 수 있다.
10^11 = ((10^5 % 12) × (10^5 % 12) × 10) % 12
이때 (10^5 % 12)은 또 다음과 같이 쪼갤 수 있다.
= ((10^2 % 12) × (10^2 % 12) × 10) % 12
이를 일반화하면 다음과 같은 식으로 나타낼 수 있다.
((A^(B//2) % C) × (A^(B//2) % C) × A) % C
지수가 1이 될 때까지 쪼개고 쪼개기를 반복해서
최대한 작은 수를 만드는 것이다.
이를 그림으로 설명하면 다음과 같다.
이처럼 방대한 문제를 작은 문제들로 분할한 다음
각각을 해결하여 합치는 방법을 분할 정복이라고 한다.
분할 정복은 보통 재귀 함수로 구현한다.
➌ 정답 코드
A, B, C = map(int, input().split())
def power(A, B, C):
if B == 1:
return A % C
temp = power(A, B // 2, C)
if B % 2 == 1:
return (temp * temp * A) % C
else:
return (temp * temp) % C
print(power(A, B, C))분할 정복을 이용하여 파이썬으로 코드를 구현해보았다.
지수인 B가 1이 될 때까지 자기 자신(power)을 재귀적으로 호출한다.
끝!
잘못된 정보, 오탈자를 발견하면 편하게 댓글로 말씀해주시면 감사하겠습니다 🙂
