재귀란?
하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
재귀를 이용해 문제를 풀때는 수학적 귀납법을 이용하면 간결하게 풀 수 있다.
제일 앞의 도미노를 쓰러트리면 모든 도미도는 쓰러질 것이다.
그런데 왜? 모든 도미노가 쓰러지는가를 설명해보자
첫번째 설명 방법은 제일 앞에 있는 1번 도미노가 쓰러지면 2번도미노, 3번도미노... 순차적으로 쓰러진다는 설명방법이고
두번째 설명 방법은 1번 도미노가 쓰러진다. K번 도미노가 쓰러지면 K+1번 도미노도 쓰러진다 결국에는 모든 도미노가 쓰러진다는 귀납적 방식을 이용한다.
절차지향적 사고방식)
// N~1까지 차례대로 출력
void func1(int val) {
if (val == 0) return;
cout << val << '\n';
func1(val - 1);
}
func1(3);
func1(10000...) 일 경우 절차지향적 방식으로 생각한다면 매우 오래걸릴 것이다.
만약 재귀함수의 로직이 복잡하다면 머리속이 혼란스러워진다.
귀납적 사고방식)
func1(1) -> 1을 출력한다
func1(2) -> 2, 1을 출력한다
첫번째는 func1(k)가k, k-1, k-2 ... 1을 출력한다.
두번째는 func1(k+1)이 호출되면 k+1을 출력하고 func1(k)를 호출하게 된다.
그러므로 func1(k+1)은 k+1, k, k-1 ... 1까지 차례로 출력한다.
즉, 첫번째와 두번째 문장이 참이므로 귀납적으로 func1 함수가 n~1까지 차례대로 출력하는 함수이다.
재귀함수의 조건
특정입력에 대해서 자기 자신을 호출하지 않고 종료되어야 함(Base condition)
예시를 들면, 이 코드에서 val가 0일때(특정입력) 자기 자신을 호출하지 않고 종료가 되니 이것이 Base condition이고 이 함수에 자연수만 넣는다는 조건하에 모든 입력은 결국 0으로 수렴하게 된다.
Base condition이 없거나 함수에 인자값으로 들어가는 수가 잘못되면 무한루프에 빠지다가 런타임 에러가 발생한다.
void func1(int val) {
if (val == 0) return;
cout << val << '\n';
func1(val - 1);
}
재귀에 대한 Tip
Tip 1)
1. 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정의
2. 모든 재귀함수는 반복문으로 동일한 동작을 하는 것처럼 만들 수 있음
3. 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서 손해를 봄
Tip 2)
재귀함수가 자기 자신을 여러 번 호출하게 되면 예상과는 다르게 비효율적인 경우도 있음
다음은 피보나치 수열에 대한 문제인데 base condition은 n=1 일때 이다.
이미 계산된 값이 다시 계산되는 일이 빈번하게 발생하면서 시간복잡도는 n에 대한 지수함수 만큼의 시간이 걸리게 된다.
Tip 3)
재귀함수가 자신을 부를 때 stack 영역에 함수에 대한 정보가 저장됨
(메모리 구조와 관련된 내용에 대해서 모른다면 면접을 위해서라도 정리가 꼭 필요!)
알고리즘 문제를 풀 때 메모리 제한이 있기 때문에 stack의 일정 메모리 크기를 넘어가지 않도록 코드를 작성해야 함
백준 1629)
a를 b만큼 곱했을 경우 만약에 a가 21억이고 b가 2만 되도 int 자료형의 크기인 약 21억을 넘어가기 때문에 overflow가 발생해서 문제를 풀 수 없다.
곱하는 중간마다 계속 m으로 나눠서 나머지만 챙기는 방식으로도 풀 수 있는데
a(12), b(13), c(14)를 곱했을 때 일의자리만 구하려고 한다면 각 수의 일의 자리만 곱해서 일의 자리만 뽑아내면 된다.
2 * 3 * 4 = 24 -> 일의자리(4)
이러한 방식과 마찬가지로 a = 5, b = 4, m = 3 일때
5를 4번 곱한다음에 3으로 나누는 방식으로 풀 수 있지만 아주 큰 숫자라면 반복문을 돌 때 자료형의 크기를 넘어가서 overflow가 발생할 수 있다.
이를 해결하기 위해서 5를 n번 곱할때 마다 m으로 나눈값의 나머지를 결과값(val)에 넣어준다.
초기값 val = 1
5를 1번 곱하는 경우 : val * 5 % 3 = 2(나머지는 val값에 저장)
5를 2번 곱하는 경우 : val * 5 % 3 = 1(나머지는 val값에 저장)
5를 3번 곱하는 경우 : val * 5 % 3 = 2(나머지는 val값에 저장)
5를 4번 곱하는 경우 : val * 5 % 3 = 1(나머지는 val값에 저장)
5를 여러번 곱하고 3으로 나누는 경우와 비교
1 * 5 = 5
5 * 5 = 25
5 * 5 * 5 = 125
125인 최종 결과값을 3으로 나눈 나머지는 2가 나오게 되는데 중간중간 나누는 경우와 나머지 값이 동일하다.
그러나 문제에서 b의 값이 약 21억이 되기 때문에 최대 21억번 반복문을 도는 동안 CPU는 1초 동안 약 20억번 연산을 한다고 가정했을 때 O(N)으로 해결할 수 없다.
우리가 5를 4번 곱하고 3으로 나눈다고 했을 때,
5를 2번 곱하고 3으로 나눈 나머지 값에 5를 2번 곱하고 3으로 나눈 나머지 값을 한번더 곱해주면 된다.
만약 5를 5번 곱하고 3으로 나눈다고 했을 때,
이전 경우에는 딱 반으로 나누어지기 때문에 제곱을 했지만 홀수인 경우에는 제곱을 한다음에 마지막 남은 5를 한번더 곱해서 나머지를 구해야 한다.
이거를 귀납법으로 나타내보자
1번 도미노가 쓰러지면 2번 도미노도 쓰러진다.
k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.
1승을 계산했으면 2승은 1승을 거듭제곱한 결과이다.
K승을 계산했으면 2k승과 2k+1승도 O(1)에 계산할 수 있다.
문제로 돌아가서 이 귀납법을 적용하면 5를 4번 곱하고 m으로 나누는 경우 4승의 반인 2승을 계산하고 나중에 5의 2승을 한번더 곱하면 된다. 1승인 경우 더 이상 반으로 나눌 수 없으므로 1승이 되면 재귀함수를 호출하지 않고 결과를 리턴한다.
#include<iostream>
using namespace std;
using LL = long long;
LL func1(LL a, LL b , LL m) {
if (b == 1) return a % m;
LL val = func1(a, b / 2, m);
// 짝수개인 경우 or 홀수개인 경우
val = val * val % m;
if (b % 2 == 0) return val;
else return val * a % m;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
LL a, b, c;
cin >> a >> b >> c;
cout << func1(a, b, c);
return 0;
}
재풀이 코드
거듭제곱이 짝수인 경우 예시)
20억을 2번 거듭제곱해서 m으로 나누어서 나머지를 구할 수도 있지만, 시간제한이 0.5초기 때문에 O(n) 시간복잡도로 풀지 못한다. 최대 n번(21억번) 거듭제곱시 CPU 연산이 1초에 20억번 연산을 한다고 가정했을 때 0.5초에 10억번 연산을 해야되므로 시간초과가 발생한다.
n을 반으로 분할해서 똑같은 n을 n*n = 2n(지수승) 계산하면 O(logN) 시간복잡도가 발생한다.
거듭제곱이 홀수인 경우 예시)
