목차
0x00 재귀 알고리즘 설명
0x01 연습문제1 - 거듭제곱
0x02 연습문제2 - 하노이 탑
0x03 연습문제3 - Z
0x00 재귀 알고리즘 설명
재귀를 이해하고 문제를 푸는 것은 익숙해지기에 시간이 좀 걸린다.
순서대로 생각하는 절차지향적 사고와는 차이가 있기 때문이다. 마음 단단히 먹고 시작하기.
재귀란?
하나의 함수에서 자기 자신을 다시 호출해 작업하는 알고리즘이다.
재귀로 N부터 1까지 출력하는 함수와, 1부터 N까지 합을 구하는 함수를 혼자 구현해보자.
[ N부터 1까지 출력하는 함수 ]
void printrec(int num){
if(num == 0) return;
cout << num << ' ';
return printrec(num-1);
}
// 출력: 10 9 8 7 6 5 4 3 2 1[ 1부터 N까지 합을 구하는 함수 ]
int rec(int num){
if(num == 1) return num;
return rec(num-1) + num;
}
// rec(n);
// 출력: 55(바킹독님 코드와 똑같아서 내코드 그대로 적어놓음)
재귀로 푼다는 것의 의미가 뭘까?
방금 짠 재귀 코드가 왜 올바른 결과를 주는지 제대로 이해해보자.
우리가 어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것이다.
아래 사진의 도미노 사진을 보자. 맨 앞의 1번 도미노를 쓰러뜨리면 모든 도미노가 쓰러진다.
왜 그렇게 되는지 설명하는 방법에는 두 가지 방법이 있다.
첫 번째 방법
1번 도미노가 쓰러지면 2번 도미노가 쓰러진다. 2번 도미노가 쓰러지면 3번 도미노가 쓰러진다. 3번 도미노가 쓰러지면 ...
두 번째 방법 (수학적 귀납법)
'1번 도미노가 쓰러진다. '
'k번 도미노가 쓰러지면 k+1번 도미노가 쓰러진다'
이 두 문장은 참이다. 그러므로 1번 도미노가 쓰러지면 모든 도미노가 쓰러진다.
즉, 우리에게 익숙한 절차지향적인 사고를 탈피해야 귀납법에 익숙해질 수 있다.
N부터 1까지 출력하는 함수를 귀납법으로 생각해보자
void func1(int n){
if(n == 0) return;
cout << n << ' ';
func1(n-1);
}
// func1(3) 출력: 3 2 1우선 절차지향적으로 func1(3)의 출력 결과가 왜 3 2 1 인지 생각해보자.
코드의 흐름을 그대로 따라가면 된다.
func1(3) 이 호출되면 3을 출력한다. 그리고 func1(2) 를 호출한다.
-> func1(2)이 2를 출력한 후, func1(1) 호출한다.
-> func1(1)이 1을 출력한 후, func1(0)을 호출한다.
-> func1(0)이 호출되어 return 함수가 종료된다.
귀납적 사고로 이해해보자.
첫 째로, func1(1)이 1을 출력한다. 이건 굉장히 자명하다.
그 다음이 관건인데,
func1(k)가 k, k-1, k-2 ... 1을 출력하면, 즉 k부터 1까지 차례로 출력하면
func1(k+1)은 k+1부터 k, k-1, k-2 ... 1 까지 차례로 출력한다는 것을 보여야한다.
이를 위해 func1(k+1)이 호출될 때 어떻게 되는지 확인하면 된다.
func1(k+1)을 호출하면, k+1을 출력하고 func1(k)를 호출한다.
그리고 func1(k)는 k부터 1까지 차례로 출력하는 가정을 했으니 func1(k+1)은 k+1부터 1까지 차례로 출력함을 알 수 있다.
이 두 문장이 참이므로 귀납적으로 func1함수가 n부터 1까지 차례로 출력하는 함수임을 알 수 있다.
재귀 함수의 조건
앞의 예시를 통해 귀납법에 익숙해지길 바라며 재귀 함수의 조건을 알아보자.
올바른 재귀 함수는 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료해야 한다.
이러한 입력을 base condition (==base case)라고 한다.
그리고 모든 입력은 base condition으로 수렴해야 한다.
int func2(int n){
if(n == 0) return 0;
return n+func2(n-1);
}위 코드는 n==0 일 때, 자기자신을 호출하지 않고 종료된다. 이것이 base condition이다.
그리고 이 함수에 자연수만 넣을 테니 모든 입력은 결국엔 n==0으로 수렴하게 된다.
이 두 조건을 지키지 않으면 무한루프에 빠져서 런타임 에러가 발생한다.
재귀 함수의 조건과 정보
1. 재귀 함수의 인자, 로직, 종료 조건을 명확하게 정의해야 한다.
2. 재귀는 코드를 간결하게 만들어줄 수 있지만, 메모리/시간에서는 손해를 본다는 것을 인지하자.
굳이 재귀를 쓰지 않아도 구현이 된다면 반복문으로 코드를 짜는 것이 좋다.
3. 한 함수가 자기 자신을 여러번 호출하게 되면 비효율적일 수 있다.
아래 코드는 피보나치 함수다.
int fibo(int n){
if(n <= 1) return 1;
return fibo(n-1) + fibo(n-2);
}fibo(5)는 fibo(4)와 fibo(3)을 호출한다.
fibo(4)는 fibo(3)과 fibo(2)를, fibo(3)은 fibo(2)와 fibo(1)을 호출한다.
-> 이미 계산한 값을 또 계산하게 된다!
-> 시간 복잡도가 말도안되게 커져버린다.
-> 나중에 다이나믹 프로그래밍으로 O(n)에 해결하는 방법을 배운다.
4. 재귀 함수가 자기 자신을 부를 때 스택 영역에 계속 누적된다.
운영 체제의 메모리 공간을 보자. 제일 높은 주소 쪽에 컴파일 타임에 크기가 결정되는 stack 영역이 있다.
stack영역은 지역변수와 함수의 호출정보(stack frame)가 저장되는데, 함수가 종료 되야 소멸한다.
문제를 풀 때 메모리 제한이라는 것이 있다.
일부 컴파일 환경에는 stack영역 메모리 제한이 별도로 1MB로 제한되어 있기도 한다.
BOJ는 스택 메모리의 제한이 없지만 swexpertacademy.com에는 제한이 걸려 있다.
그래서 이 코드 처럼 재귀를 10만번 정도만 돌아도 스택 1MB를 초과하여 런타임 에러가 발생한다.
BOJ에 제출하면 "맞았습니다."가 뜨는 남의 코드를 로컬에서 돌렸을 때 계속 런타임 에러가 뜬다면,
가장 의심해 볼만한건 재귀가 너무 깊거나 지역변수로 지나치게 큰 크기의 배열을 잡았을 경우다.
0x01 연습문제1 - 거듭제곱
a의 b제곱을 m으로 나눈 나머지를 구하자.
int func1(int a, int b, int m){
int val = 1;
while(b--) val *= a;
return val % m;
}방법1
a를 b번 곱한다. 그 결과를 m으로 나눈 나머지를 출력한다.
하지만 '방법1'은 제대로 동작하지 않는다. 만약 func1(6, 100, 5)를 넣으면 0이 나온다.
이유를 고민해보자.
.........
using ll = long long;
ll func1(ll a, ll b, ll m){
ll val = 1;
while(b--) val = val * a % m;
return val;
}그 이유는 바로 int overflow가 발생하기 때문이다.
6의 100제곱은 int의 범위를 까마득하게 벗어난다. 이것을 해결해주려면 중간 중간 계속 m으로 나눠서 나머지만 챙겨가면 된다.
방법2
a를 1번째 곱한다. m으로 나눈 나머지를 a에 대입한다.
a를 2번째로 곱한다. m으로 나눈 나머지를을 a에 대입한다.
.... a를 b번째 곱한다. m으로 나눈 나머지를 출력한다. -> 이렇게 중간 계속 m으로 나눠서 나머지만 챙기기.
a를 b번 곱하는 방식으로는 계산할 수 없다면 어떻게 할까?
백준 1629번 곱셈 문제를 풀어보자.
자연수 A, B, C가 주어진다. A를 B번 곱한 수를 C로 나눈 나머지를 출력하라.
(A, B, C는 모두 2,147,483,647 이하의 자연수이다. 시간제한 0.5초)
힌트를 읽어보자.
a의 n승을 제곱하면 a의 2n승이 된다.
12의 58승과 12의 116승의 관계를 보자.
12의 58승을 67로 나눈 나머지가 4라면, 12의 116승을 67로 나눈 나머지는 (4의 제곱) 즉, 16이 된다.
-> 58승을 계산할 수 있으면 116승을 계산할 수 있다.
-> k승을 계산할 수 있으면 2k승과 2k+1승도 O(1)에 계산할 수 있다.
이 두 문장은 참이다. 따라서 a의 임의의 지수승을 귀납적으로 계산할 수 있다.
귀납법의 일부를 코드로 바꿔보자.
func(a, b, c)는 func(a, b/2, c)를 기반으로 구할 수 있다.
using ll = long long;
ll func(ll a, ll b, ll c){
val = func(a, b/2, c);
val = val * a % c; // a를 곱하고 c로 나눈 나머지
}
// func(a, b, c)는 func(a, b/2, c)를 기반으로 구할 수 있다.만약 b가 짝수라면 val을 그대로 리턴한다.
만약 b가 홀수라면, "곱하기 a 하고 c로 나눈 나머지"를 한 번 더 수행한다.
아래는 완성된 풀이코드다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll A, B, C;
ll rec(ll a, ll b, ll c){
if(b == 1) return a % c; // a가 c보다 클 수 있기 때문에 a % c를 반환.
ll val = rec(a, b/2, c);
val = val * val % c;
if(b%2 == 0) return val;
return val * a % c; // b가 홀수라면 *a %c 를 한 번 더 수행.
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> A >> B >> C;
cout << rec(A, B, C);
return 0;
}
// http://boj.kr/9c320eecca4b4958bd54977f83371a36이 함수의 시간 복잡도는 b가 계속 절반씩 깎이니까 O(log b)이다.
그래서 문제의 시간 제한을 넉넉히 지킬 수 있다.
0x02 연습문제2 - 하노이 탑
두 번째 문제는 재귀 문제 중에 스테디셀러인 하노이탑 문제다.
온라인 게임으로 원판 3, 4, 5개일 때를 깨고 오자. 하노이탑 문제가 뭔지 감이 올 것이다.
그리고 백준 11729번 하노이 탑 이동순서 문제를 읽고 오자.
읽고나서 드는 느낌은 '막막하다...?' 일단 n번 원판에만 집중해보자.
어찌됬든 원판들을 전부 기둥1에서 기둥3으로 옮기려면,
제일 아래 있는 n번 원판을 기둥1에서 기둥3으로 옮겨야 한다.
그런데 n번 원판을 옮기려면 n-1번부터 1번까지의 원판들이 비켜줘야 하고 나아가 그것들이 기둥2에 가있어야 한다.
왜냐하면 작은 원판 위에 큰 원판을 둘 수 없다는 규칙 때문이다.
n-1개의 원판을 기둥2로 옮긴다.
그리고 n번 원판을 기둥3으로 옮긴다.
이 다음에는 어떻게 해야 할까?
n-1개의 원판을 기둥2에서 기둥3으로 옮기면 된다.
과정을 보면, n-1개의 원판을 원하는 곳으로 옮길 수 있으면 n개의 원판을 처리할 수 있다.
구현을 위해 단계적으로 생각해보자.
1. 함수의 정의
func(n)함수가 func(n-1)함수를 호출하는 방법이 가능할까?
문제 요구사항은 원판 n개를 기둥a에서 기둥b로 옮기는 방법을 출력하는 것이다. 따라서 func(n-1)은 이 문제에 부적절하다.
따라서 아래처럼 정의하자.
void func(int a, int b, int n)2. base condition
재귀가 자기자신을 호출하지 않고 종료하는 조건을 정의하자.
원판 1개인 경우를 생각해보자.
n=1 일 때, a에서 b로 옮기도록 하면 된다.
n=1 일 때, cout << a << ' ' << b <<'\n';3. 재귀 식
기둥 a에서 기둥 6-a-b로 옮긴다.
이건 바로 이해가 안 갈 수 있다. 기둥 번호 1, 2, 3번의 합이 6이라는 것을 생각하면서 아래의 재귀식을 읽어보자.
방금 봤던 이동순서 그림을 다시 보고 오면 도움이 된다.
n번 원판을 기둥 a에서 기둥 b로 옮긴다. --> n번 원판을 기둥 1에서 기둥 2로 옮긴다.
n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다. --> n-1개의 원판을 기둥 1에서 기둥 3으로 옮긴다.
기둥1을 기둥a라는 공통의 출발지로 본다면,
n-1개의 원판은 6-a-b로 옮겨야 하고, n번 원판은 b로 옮겨야 한다.
n-1개의 원판을 기둥a에서 기둥 6-a-b로 옮긴다. func(a, 6-a-b, n-1);
n번 원판을 기둥 a에서 기둥b 로 옮긴다. cout << a << ' '<< b << '\n';
n-1개의 원판을 기둥 6-a-b에서 기둥b로 옮긴다. func(6-a-b, b, n-1);4. 원반을 옮긴 횟수
원반 k개를 옮기기 위해 A번 이동이 필요하다고 하자.
그러면 원반 k+1개를 옮길 때는 몇 번이 필요할까?
k개의 원판을 빈 곳으로 옮길 때 A번, (이미 알고 있다)
k+1번 원판을 옮길 때 1번,
k개 원판을 다시 빈 곳에서 목적지로 옮길 때 A번이 필요하다.
-> 즉, 2A+1번 이동이 필요하다.
//바킹독님코드 http://boj.kr/f2440915dca04aaa9aec759080516973
#include <bits/stdc++.h>
using namespace std;
void func(int a, int b, int n){
if(n == 1){
cout << a << ' ' << b << '\n';
return;
}
func(a, 6-a-b, n-1);
cout << a << ' ' << b << '\n';
func(6-a-b, b, n-1);
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int k;
cin >> k;
cout << (1<<k) - 1 << '\n'; // (1<<k)는 2의 k승이다.
func(1, 3, k);
}
0x03 연습문제3 - Z
하노이탑이 아리송하지만. 백준 1074번 Z문제를 읽어 보면 '또 뭔가..' 싶을 것이다.
꾹 참고 5분만 재귀 관점으로 고민해보자.
방문 순서가 어떤 식으로 매겨지냐면, 배열을 4등분 한 후에, 1,2,3,4 순으로 진행된다.
아래 그림에서 N=3일 때, 16x16 배열을 그려놓고. 4등분 해서 영역 1,2,3,4로 나눠놨다.
r=2, c=2 칸은 '영역1'에서' 12번째로 방문한다.
'영역1' 내부를 4등분으로 나누면, 영역 1, 2, 3에 포함된 0칸~11칸을 전부 방문하고, 12번째로 방문한 셈이다.
r=6, c=2 칸은 '영역3'에서 44번째로 방문한다.
'영역3'에 오기 전에는 이미 '영역1, 영역2'를 방문한다. '영역3'내부의 0칸~11칸을 전부 방문하고, 12번째로 방문한 셈이다.
뭔가 이전에 방문한 순서를 기반으로 다음 것을 구할 때 써먹을 수 있을 것 같다는 느낌이 조금 온다. (그저 느낌뿐..)
구현을 위해 단계적으로 생각해보자.
1. 함수의 정의
직관적으로 보이는 모양 대로 정의하면 된다. 2의 N승 배열에서, (r,c)를 방문하는 순서를 반환하는 함수.
이 값이 Int범위에 들어오는지 신경써줄 필요가 있는데, n은 15이하니까 int범위를 초과하지 않는다.
int func(int n, int r, int c)2. base condition
n=0일 때 0을 반환하도록 하자.
n=0 일 때, return 0;3. 재귀 식
각 상황에 따른 반환 값은 아래와 같다.
여기서 half는 한 변 길이의 절반, 즉 2의 n-1승이다.
(r,c)가 1번 영역일 때, return func(n-1, r, c);
(r,c)가 2번 영역일 때, return half*half + func(n-1, r, c-half);
(r,c)가 3번 영역일 때, return 2* half*half + func(n-1, r-half, c);
(r,c)가 4번 영역일 때, return 3* half*half + func(n-1, r-half, c-half);아까 그림을 보며 확인한 12번째 방문한다는 것의 의미를 다시 보자.
12번째 방문한다는 것은 0칸~11칸을 전부 방문하고, 12번째로 방문하는 것이다.
2의 2승 을 4등분한 영역에서, 2의 1승(2의 n-1승) 영역의 1,2,3영역을 모두 방문한 다음에 4영역을 방문하고 있는 것이다.
// http://boj.kr/fd805e1226e949f9b6b2eff59e5be642
#include <bits/stdc++.h>
using namespace std;
int func(int n, int r, int c){
if(n == 0) return 0;
int half = 1<<(n-1);
if(r < half && c < half) return func(n-1, r, c);
if(r < half && c >= half) return half*half + func(n-1, r, c-half);
if(r >= half && c < half) return 2*half*half + func(n-1, r-half, c);
return 3*half*half + func(n-1, r-half, c-half);
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
int n, r, c;
cin >> n >> r >> c;
cout << func(n, r, c);
}재귀 문제집
| 백준 문제 | 내 코드 |
| 1629번 곱셈 | 곱셈 내 코드 |
| 11729번 하노이 탑 이동 순서 | 하노이 탑 이동순서 내코드 |
| 1074번 Z | |
| 17478 재귀함수가 뭔가요? | 재귀함수가 뭔가요? 내코드 |
| 1780번 종이의 개수 | |
| 2630번 색종이 만들기 |
다음 시간에 배울 백트래킹을 잘 해내기 위해서라도 재귀를 능숙하게 다룰 수 있도록 연습을 많이 하자. 반복 또 반복.
문제집에 있는 문제들이 쉽지는 않겠지만,
풀이를 보고 푸는 한이 있더라도 재귀가 두렵지 않을 때 까지 연습을 한 후에 백트래킹으로 넘어가자.
다음 시간에는 백트래킹을 공부한다.
공부 자료 출처 : 바킹독 알고리즘 재귀
'알고리즘 > 실전 알고리즘' 카테고리의 다른 글
| 0x0E강 - 정렬1 (0) | 2021.12.11 |
|---|---|
| 0x0C강 - 백트래킹 (0) | 2021.12.10 |
| 0x0A강 - DFS (0) | 2021.12.07 |
| 0x09강 - BFS (0) | 2021.12.07 |
| 0x08강 - 스택의 활용(수식의 괄호 쌍) (0) | 2021.11.29 |