Today I learned : recursion
오늘 할 일
바킹독 재귀
바킹독의 실전 알고리즘 : 재귀 (15일 내용 이어서)
연습 문제 1 : 1629번 곱셈
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll pow_recur(ll a, ll b, ll m){
if(b==1) return a%m; //b가 1이면 그냥 본인만
ll val= pow_recur(a,b/2,m); //b/2로 재귀 호출
val=val*val%m; //반절 나눈 지수대로 val*val -> 지수 2n
if(b%2==0) return val; //짝수이면 그대로 반환
return val*a%m; // b가 홀수이면 한 번 더 곱해서(2n+1) 반환
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
ll a,b,c;
cin>>a>>b>>c;
cout<<pow_recur(a,b,c);
}
위 코드에서 pow_recur 함수가 a^b mod m을 계산해주는 함수이다. 이전 내용에서 재귀 함수에서 정의해야 되는 부분은 아래와 같았다.
- 함수의 정의 -> a의 b제곱을 계산해주는 함수(mod m 상황에서)
- base condition -> b가 1이면 본인 호출 a의 1승은 a이므로.
- recursion 식 ->
바킹독에서 하는 말이, 절차지향적 사고 대신 귀납적인 사고로 코드를 이해하라고 한다.
- base condition 잘 잡고
- k승의 결과를 토대로
- 2k, 2k+1승의 결과도 계산 가능하니 재귀가 가능하다..고 함수를 이해할 필요가 있다고 한다(모르겠다……..)
여기서 시간복잡도는 b가 계속 절반씩 깎이기 때문에 O(log b)이다.
연습 문제 2 : 11729번 하노이 탑 이동 순서
- base condition 잘 잡고 -> 2번에 n이 1개일 때
- k의 결과를 토대로 -> n-1개는 2번에 가있고 n은 1에서 3으로
-
2k, 2k+1의 결과도 계산 가능하니 ->
- n-1개의 원판을 1에서 2로 옮기면
- n번째 원판을 1에서 3으로 옮길 수 있고
- 나머지 n-1개의 원판을 2에서 3으로 옮기면 된다
- 그러면 base conditon은 2(1도 가능은 함)
int N,K;
void move_recur(int n){
if(n==1){
cout<<"1 3\n";
return;
}
//n-1개의 원판을 1에서 2로 옮기기
move_recur(n-1);
cout<<"1 2\n";
cout<<"1 3\n";
cout<<"2 3\n";
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>N;
K=(N-1)*3+1;
cout<<K<<'\n';
move_recur(N);
}
일단 이렇게 짜다가 끝났는데 함수 하나로는 안되고 각 출력마다의 func을 두어야 할 거 같긴 하다. 그냥 해설 보자..ㅜㅜ
- 함수의 정의
여기서도 func(int n)은 적절하지 않다고 한다. func(int a, int b, int n)로 두어서 원판 n개를 a에서 b로 두는 방법을 출력하는 함수로 두어야 한다.
일단 여기까지만 하고 다시 내가 짜보자.
#include <bits/stdc++.h>
using namespace std;
/*
1. n-1개의 원판을 1에서 2로 옮기면
2. n번째 원판을 1에서 3으로 옮길 수 있고
3. 나머지 n-1개의 원판을 2에서 3으로 옮기면 된다
4. 그러면 base conditon은 2(1도 가능은 함)
*/
int N,K;
void move_recur(int a, int b, int n){
if(n==1){
cout<<a<<' '<<b<<'\n';
return;
}
//n-1개를 b에서 b+1로 옮기기
move_recur(a,6-a-b,n-1);
cout<<a<<' '<<b<<'\n';
move_recur(6-a-b,b,n-1);
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>N;
K=(1<<N)-1; //-> 이건 대입으로 찾는 게 나을듯 (하노이는 2^n-1 외우기)
cout<<K<<'\n';
move_recur(1,3,N);
}
위와 같이 작성했더니 풀렸다.
- base condition
위 코드와 같이 n==1이 맞았다. 근데 n==0일 때 코드가 더 예쁘게 완성된다고 한다.
- 재귀 식
한가지 주의할 점이 처음에는 % 이용해서 기둥 1,2,3을 표현하려고 했었는데 나머지에 0도 있다는 것을 까먹고 있었다. 또한, 여기서는 1,2,3기둥이 순환한다는 보장이 없고 “남은” 기둥을 써야한다는 점이 중요하기에 1,2,3의 총합인 6에서 a기둥과 b기둥을 빼주는 것이 중요하다.
연습 문제 3 : 1074번 Z
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int N,r,c;
int cnt;
pair<int,int> cur;
void vis_recur(int a,pair<int,int> n){
/*
1. 함수 정의 -> 2의 a승일 때 호출, 좌표와 함께
2. base condition -> 좌표 간 2^1일 때
3. 재귀 호출
*/
//이때 n은 맨끝 좌표
if(a==1){
if(cur.X-1==r&&cur.Y-1==c) cout<<cnt+1; else cnt++;
if(cur.X==r&&cur.Y-1==c) cout<<cnt+1; else cnt++;
if(cur.X-1==r&&cur.Y==c) cout<<cnt+1; else cnt++;
if(cur.X==r&&cur.Y==c) cout<<cnt+1; else cnt++;
return;
}
vis_recur(a-1,{(cur.X)/2,(cur.Y)/2});
vis_recur(a-1,{(cur.X),(cur.Y)/2});
vis_recur(a-1,{(cur.X)/2,(cur.Y)});
vis_recur(a-1,{(cur.X),(cur.Y)});
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>N>>r>>c;
vis_recur(N,{1<<N,1<<N});
}
제미나이 채점 돌려보니까 논리는 맞는데 전체 판을 다 돌리면 시간 초과가 발생한다고 한다. 바킹독으로 돌아가서 풀이 확인해보자.
바킹독에서는 재귀 함수를 아래와 같이 정의했다.
- 함수의 정의 -> func(int n, int r, int c)
(r,c)를 방문하는 순서를 반환하는 함수
- base condition
n=0일 때 return 0;
- 재귀 식
사분면으로 나누어서 func(n-1,r,c), half*half+func(n-1,r,c-half) 이런 식으로…
여기서 half는? 사분면의 반절 쪼개서 그 넓이. 그 넓이는 이미 순회를 했을 테니까 더해주는 것이다. 다시 정리하자면…
- (r,c)가 1사분면에 있을 떄 -> return func(n-1,r,c);
- (r,c)가 2사분면에 있을 때 -> half*half+func(n-1,r,c-half);
- (r,c)가 3사분면에 있을 때 -> 2halfhalf+func(n-1,r-half,c);
- (r,c)가 4사분면에 있을 때 -> 3halfhalf+func(n-1,r-half,c-half);
잠깐. 좌표에서는 왜 half를 빼주는지 생각해보자. 아, 다른 사분면은 더해주고 다시 그 작은 정사각형에서의 좌표가 리셋되기 때문이다.
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int N,r,c;
int cnt;
pair<int,int> cur;
int vis_recur(int n,int a, int b){
if(n==0) return 0;
int half=1<<(n-1); //2의 (n-1)승
if(a<half && b<half) return vis_recur(n-1,a,b); //1사분면
if(a<half && b>=half) return half*half+vis_recur(n-1,a,b-half);
if(a>=half && b<half) return 2*half*half+vis_recur(n-1,a-half,b);
if(a>=half && b>=half) return 3*half*half+ vis_recur(n-1,a-half,b-half);
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>N>>r>>c;
cout<<vis_recur(N,r,c);
}
최종본이다. 재귀를 잘 이해한 뒤에 백트래킹을 듣는 게 좋다고 한다(미리 알았더라면 벼락치기 하지 않았을 텐데..)
회고
연휴 동안 프세카 하느라 할 일을 미뤘다. 미뤄도 되겠지 했는데 생각보다 할 게 많더라. 큰일이다… 알고보니 약속도 많아서 시간 쪼개서 얼른 해야될 거 같다.