모든 입력은 base condition으로 수렴해야 한다.
인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다.
모든 재귀 함수는 반복문만으로 동일한 동작을 할 수 있다.
반복문으로 구현했을때에 비해 코드가 간결해지지만 메모리와 시간에서 손해를 본다.
재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 된다.
재귀함수를 절차적으로 계속 따라들어가며 생각하면 답이없다. 절차지향적인 사고를 탈피해야 한다.
재귀함수 예제문제들을 풀어보니 문제에 귀납적인 내용이 적혀있다. 이걸 토대로 구현하면 될 것 같다.
작거나 큰 문제를 확장시키거나 쪼개간다는 점에서 DP와 개념은 비슷한데 memoization이 사용되지 않는다는 점이 차이인 것 같다.
연습 문제
1629: 곱셈
더보기
#include <iostream>
using namespace std;
using ll = long long;
ll powmod(ll a, ll b, ll c)
{
if (b == 1) return a % c;
ll val = powmod(a, b / 2, c);
val = val * val % c;
if (b % 2 == 0) return val;
else return val * a % c;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll a, b, c;
cin >> a >> b >> c;
cout << powmod(a, b, c);
return 0;
}
a^b = a^b/2 * a^b/2
(a*b)%c = (a%c)*(b%c)%c
위 두개를 알아야 한다. 그리고 b가 홀수인 경우 a를 한번 더 곱해줘야 한다는 걸 주의해야 한다.
큰 문제를 작은 문제로 쪼개서 해결한다는 점에서 뭔가 DP랑 유사한 것 같다.
11729: 하노이 탑 이동 순서
더보기
#include <iostream>
using namespace std;
void tower_of_hanoi(int n, int start, int dest)
{
if (n == 1)
{
cout << start << " " << dest << '\n';
return;
}
tower_of_hanoi(n - 1, start, 6 - start - dest);
cout << start << " " << dest << '\n';
tower_of_hanoi(n - 1, 6 - start - dest, dest);
return;
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
cout << (1 << n) - 1 << '\n';
tower_of_hanoi(n, 1, 3);
return 0;
}
n이 성립되면 n-1도 성립되는것을 이해해야 한다.
n-1을 2번, n을 3번, n-1을 3번으로 옮긴다는 것을 알면 금방 풀 수 있는 문제이다.
즉, 귀납적 사고법이 반드시 필요한 문제.
1074: Z
더보기
#include <iostream>
using namespace std;
int z_search(int n, int r, int c)
{
if (n == 0) return 0;
int half = 1 << (n - 1);
if (r < half && c < half) return z_search(n - 1, r, c);
else if (r < half && c >= half) return half * half + z_search(n - 1, r, c - half);
else if (r >= half && c < half) return 2 * half * half + z_search(n - 1, r - half, c);
else return 3 * half * half + z_search(n - 1, r - half, c - half);
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
// r행 c열
int n, r, c;
cin >> n >> r >> c;
cout << z_search(n, r, c);
return 0;
}
재귀의 n값마다 행과 열의 사분면을 파악해서 재귀 호출이 달라져야한다.
예를들어 3사분면에 있다면 1-2분면의 값을 모두 더하고 나머지값은 더 작은 사분면으로 판단시키기 위해 값을 조정하여 재귀를 호출한다.
n=1일때의 사분면 판정을 생각하면 확장이 쉽다.
기본 문제
1780: 종이의 개수
더보기
#include <iostream>
using namespace std;
int paper[2200][2200];
int cnt[3];
bool same_paper_judge(int x, int y, int n)
{
int t = paper[x][y];
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (t != paper[x + i][y + j])
{
return false;
}
}
}
return true;
}
void recursion(int x, int y, int n)
{
if (same_paper_judge(x, y, n))
{
cnt[paper[x][y] + 1]++;
return;
}
int div = n / 3;
for (int i = 0; i < 3; ++i)
{
for (int j = 0; j < 3; ++j)
{
recursion(x + div * i, y + div * j, div);
}
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> paper[i][j];
}
}
recursion(0, 0, n);
for (int i = 0; i < 3; ++i)
{
cout << cnt[i] << '\n';
}
return 0;
}
9개로 나누어 분할정복 하는것이 포인트
1992: 쿼드 트리
더보기
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string quad[65];
vector<char> answer;
bool same_judge(int x, int y, int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (quad[x][y] != quad[x + i][y + j])
{
return false;
}
}
}
return true;
}
void quad_tree(int x, int y, int n)
{
if (same_judge(x, y, n))
{
answer.push_back(quad[x][y]);
return;
}
int div = n / 2;
answer.push_back('(');
for (int i = 0; i < 2; ++i)
{
for (int j = 0; j < 2; ++j)
{
quad_tree(x + div * i, y + div * j, div);
}
}
answer.push_back(')');
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
cin >> quad[i];
}
quad_tree(0, 0, n);
for (auto& a : answer)
{
cout << a;
}
return 0;
}
4개로 분할 정복 하면서 중간에 괄호를 끼워넣는게 포인트
2630: 색종이 만들기
더보기
#include <iostream>
using namespace std;
int paper[128][128];
int answer[2]; // 흰0 파1
bool same_judge(int x, int y, int n)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (paper[x][y] != paper[x + i][y + j])
{
return false;
}
}
}
return true;
}
void recursion(int x, int y, int n)
{
if (same_judge(x, y, n))
{
answer[paper[x][y]]++;
return;
}
int div = n / 2;
for (int i = 0; i < 2; ++i)
{
for (int j = 0; j < 2; ++j)
{
recursion(x + div * i, y + div * j, div);
}
}
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> paper[i][j];
}
}
recursion(0, 0, n);
for (int i = 0; i < 2; ++i)
{
cout << answer[i] << '\n';
}
return 0;
}
'알고리즘 > 바킹독의 실전 알고리즘' 카테고리의 다른 글
| [0x0D] 시뮬레이션 (0) | 2022.08.01 |
|---|---|
| [0x0C] 백트래킹 (0) | 2022.07.31 |
| [0x0A] DFS (0) | 2022.07.30 |
| [0x09] BFS (0) | 2022.07.28 |
| [0x08] 스택의 활용 (0) | 2022.07.25 |