[BOJ] C++ 1629 곱셈 - 귀납적 사고와 재귀 함수 구조 연습하기

1629번: 곱셈

예제

10 11 12

ans : 4

---

a^b mod c를 구하는 문제이다. 가장 간단하게 생각할 수 있는 방법은 a^b을 구하고 mod c를 구하는 방법이다. 하지만 a, b, c 숫자가 모두 크기에 오버플로우도 나고, 시간초과도 뜬다. 오버플로우를 해결할 수 있는 방법은 long long 타입을 쓰면서 (a mod c)^b를 구하는 방식으로 해결할 수 있다. 이 방법은 O(b)만큼의 시간이 걸린다. 그러나 b의 크기는 매우 커서 또 시간 초과가 뜬다.

 

이 문제는 다음의 방법을 통해 귀납적 사고를 해서 재귀 구조로 구현하여 풀 수 있다.

12^58 mod 67 = 4라는 걸 알면 12^116 mod 67은 16 mod 67로 구할 수 있다. 이걸 귀납적 문장으로 정리해 보자.

 

1승의 mod C를 상수시간에 계산할 수 있다. -> base condition

k승의 mod C를 상수시간에 계산할 수 있다고 가정하면 2k승의 mod C, 2k+1승의 mod C도 상수 시간에 계산할 수 있다.

->12^116 mod 67의 예시를 통해 참임을 알 수 있다.

 

이 사고를 바탕으로 재귀 함수를 만들어보자!

만약 2k승이 입력으로 들어오면 k승을 상수시간에 계산할 수 있으므로 (A의 k승 mod C)^2 mod C 리턴

2k + 1승이 입력으로 들어오면 (A의 k승 mod C)^2 * A mod C 리턴

base condition은 1승이 입력으로 들어온 경우이다. 바로 구현해 보면

using long long ll

ll pow(ll a, ll b, ll c){
	if(b == 1) return a % c; //base condition
    ll val = pow(a, b/2, c) //k승을 상수 시간에 계산한다고 가정하는 부분이다.
    if (b % 2 == 0)	return val * val % c;
    return (val * val % c) * a % c;
}

사실 이 문제는 귀납적 사고와 재귀 함수를 구현해 보는 것을 연습하려고 푼 문제이다. 귀납적 사고까지는 어찌어찌해도 실제로 구현하기가 상당히 까다로웠다. 재귀 함수는 연습과 경험을 통해 개선된다.

 

 

 

 

 

바킹독님의 실전알고리즘을 공부하고 정리한 글입니다.

[실전 알고리즘] 0x0B강 - 재귀