알고리즘 설명
하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
수학적 귀납법을 이용해서 푼다.
재귀 함수의 조건
특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다.(Base Condition)
모든 입력은 Base Condition으로 수렴해야 한다.
재귀에 대한 정보 1
함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다.
모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
재귀는 반복문으로 구현했을 때에 비해 코드가 간결해지지만 메모리/시간에서는 손해를 본다.
재귀에 대한 정보 2
한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있다.
예: 피보나치 수열
이런 경우 DP를 사용해야 한다.
재귀에 대한 정보 3
재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 된다.
일부 운영체제에 스택 영역이 1mb로 제한이 걸려있을 수 있다.
그래서 재귀가 깊게 들어간다면 런타임 에러가 들어간다.
이 경우 반복문으로 풀어야 한다.
연습문제
BOJ_1629: 곱셈
문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
예제 입력 1
10 11 12
예제 출력 1
4
풀이
#include <bits/stdc++.h>
using namespace std;
long long func(long long a, long long b, long long c){
if(b == 1) return a % c;
long long half = func(a, b/2, c);
long long result = (half * half) % c;
if(b % 2 == 1) result = (result * a) % c;
return result;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
long long a, b, c;
cin >> a >> b >> c;
cout << func(a, b, c);
return 0;
}BOJ_11729번: 하노이 탑 이동 순서
문제
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
아래 그림은 원판이 5개인 경우의 예시이다.
입력
첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.
출력
첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
예제 입력 1
3
예제 출력 1
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3
풀이
#include <bits/stdc++.h>
using namespace std;
int cnt = 0; // 회수
ostringstream oss;
void hanoi(int len, int from, int temp, int to){
if(len == 1){
oss << from << " " << to << "\n";
cnt++;
return;
}
hanoi(len-1, from, to, temp);
oss << from << " " << to << "\n";
cnt++;
hanoi(len-1, temp, from, to);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N;
cin >> N;
hanoi(N, 1, 2, 3);
cout << cnt << "\n";
cout << oss.str();
return 0;
}팁
출력 순서를 보면 총 회수가 먼저 출력되고 하노이 계산 과정이 출력된다.
이는 하노이 계산 과정이 먼저 수행된 뒤에 총 회수를 얻는 로직의 반대 순서이다.
이럴 경우에는 cout으로 출력을 하듯 출력내용을 ostringstream에 따로 저장한 후 마지막에 str()로 추출하면 된다.
응용1 - 행렬
BOJ_1780번: 종이의 개수
문제
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.
만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.
출력
첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.
예제 입력 1
9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1
예제 출력 1
10
12
11
풀이
#include <bits/stdc++.h>
using namespace std;
array<array<int, 2200>, 2200> board;
map<int,int> cnt; // key in [-1, 0, 1], value: 개수
void recur(int len, int r, int c){
// 전체가 같은 값인지 확인, 백트래킹
int startValue = board[r][c];
bool isDiff = false;
for(int i = r; i < r + len; i++){
for(int j = c; j < c + len; j++){
if(board[i][j] != startValue){
isDiff = true;
break;
}
}
if(isDiff) break;
}
if(!isDiff){
int value = board[r][c];
cnt[value]++;
return;
}
// base condition
if(len == 1){
int value = board[r][c];
cnt[value]++;
return;
}
// recur
int preLen = len / 3;
recur(preLen, r, c);
recur(preLen, r, c+preLen);
recur(preLen, r, c+preLen*2);
recur(preLen, r+preLen, c);
recur(preLen, r+preLen, c+preLen);
recur(preLen, r+preLen, c+preLen*2);
recur(preLen, r+preLen*2, c);
recur(preLen, r+preLen*2, c+preLen);
recur(preLen, r+preLen*2, c+preLen*2);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int N;
cin >> N;
// 보드 배열 초기화
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++) cin >> board[i][j];
}
recur(N, 0, 0); // 길이, 첫 인덱스
cout << cnt[-1] << "\n";
cout << cnt[0] << "\n";
cout << cnt[1] << "\n";
return 0;
}팁
행렬을 전역으로 관리할 땐, 재귀 시 인덱스를 전역 인덱스로 넘겨줘야 한다.
행렬을 표현할 땐 (길이, 시작 행번호, 시작 열번호) 로 정의한다.
base condition까지 가지않고 선행 종료조건이 있다면 base condition 보다 앞에 작성한다. 백트래킹이라 볼 수 있다.
