[실전 알고리즘] 0x0B강 - 재귀

1. 알고리즘 설명

재귀 - 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

 

재귀로 N부터 1까지 출력하는 함수 & 1부터 N까지의 합을 구하는 함수

void func1(int n){
    if (n==0)return;
    cout << n<<' ';
    func1(n-1);
}

int func2(int n){
    if (n==0)return 0;
    return func2(n-1) + n;    
}

 

어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것이다.

 

제일 앞의 도미노를 쓰러트리게 되면 모든 도미노가 쓰러질 것이다. 그런데 왜 모든 도미노가 쓰러지는지를 설명해보라고 한다면 두 가지 방법이 있다.

 

1. 절차지향

1번 도미노가 쓰러지면 2번 도미노가 쓰러지고, 2번 도미노가 쓰러지면 3번 도미노가 쓰러지고, 3번 도미노가 쓰러지면 4번 도미노가 쓰러지고…. 이런 식으로 계속 진행되기 때문에 모든 도미노가 쓰러진다는 설명 방법이다.

 

2. 수학적 귀납법

'1번 도미노가 쓰러진다', 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다'가 참이니까 모든 도미노가 쓰러진다는 설명 방법이다.

이 두 번째 설명 방법이 맞는 이유도 결국 연쇄적으로 진행이 되어 모든 도미노가 쓰러지기 때문에 그런 것이긴 하지만 '1번 도미노가 쓰러진다', 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다' 까지만 생각한 후에 바로 모든 도미노가 쓰러진다는 결론에 도달한다.

 

 

n부터 1까지 출력하는 문제로 절차지향적 사고와 귀납적 사고의 차이를 알아보자.

1. 절차지향적 사고

func1(3)의 출력 결과가 왜 3 2 1인지를 생각해본다면 이 코드가 동작하는 흐름을 그대로 따라가면 된다.

func1(3) 호출 -> 3 출력 -> func1(2) 호출 -> 2 출력 -> func1(1) 호출 -> 1 출력 -> func1(0) 호출 ->  종료

이렇게 과정을 따라가고 나면 func1(3)을 실행했을 때 3 2 1이 출력된다는 것을 알 수 있다.

 

2. 귀납적 사고

func1(1)이 1을 출력한다. func1(k)가  k k-1 k-2 … 1을 출력하면, 즉 k부터 1까지 차례대로 출력하면 func1(k+1)은 k+1부터 1까지 차례로 출력한다는걸 보여야 한다.

k+1이 출력된 이후 func1(k)가 호출되고 func1(k)는 k부터 1까지 차례로 출력한다고 가정을 한다.

그럼 func1(k+1)은 k+1부터 1까지 차례대로 출력함을 알 수 있다.

위 두꺼운 글씨의 두 문장이 참이므로 귀납적으로 func1 함수가 n부터 1까지 차례로 출력하는 함수임을 알 수 있게 된다.

 

 

재귀 함수의 조건

특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다.(base condition | base case)

모든 입력은 base condition으로 수렴해야 한다.

 

이 두 조건 중 어느 하나라도 지켜지지 않는다면 재귀 함수는 결과를 내지 못하고 무한히 들어가다가 런타임 에러가 발생한다.

 

재귀에 대한 정보

함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지를 명확하게 정해야 한다.

그리고 모든 재귀 함수는 재귀 구조 없이 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.

재귀는 반복문으로 구현했을 때에 비해 코드가 간결해지지만 메모리/시간에서는 손해를 본다.

한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적이다. (피보나치 함수가 대표적인 예. dp로 해결 가능)

재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 된다. (메모리 제한)

---

2. 연습 문제 1 - 거듭제곱

a^b mod m

int func1(int a, int b, int m){
  int val = 1;
  while (b--) val *= a;
  return val % m;
}

int overflow 때문에 값이 다르게 나온다.

234236116 × 268921 × 29123의 일의 자리를 구할 때 직접 저 값을 계산하는 대신 각 수의 일의 자리인 6, 1, 3만 곱한 후 답이 8이라는 것을 알아낸다. 직관적으로 a × b × c의 일의 자리, 즉 10으로 나눈 나머지는 a와 b와 c 각각의 일의 자리를 구한 후 곱하면 된다는 것을 알고 있기 때문이다. 지금 코드도 10이 m으로 달라졌다는 것 뿐이지 우리가 상식적으로 알고있던 그 내용 그대로다. 그리고 type도 long long으로 바꿔주면 더 좋다. 

using ll = long long;
ll func1(ll a, ll b, ll m){
  ll val = 1;
  while(b--) val = val * a % m;
  return val;
}

코드를 보면 m 미만의 수 2개를 곱하는 상황이 계속 발생하니 m이 2^32 보다 크다면 long long의 범위조차 넘어설 수 있다. 이런 상황에서는 그냥 Big Integer 기능이 있는 JAVA 혹은 Python을 사용하거나 __int128과 같은  것을 써야 하지만 정상적인 코딩테스트라면 m이 232 보다 작을 것이므로 a^b mod m을 O(b)에 구할 수 있다.

 

그런데 b가 최대 20억이라서 O(b)로는 해결할 수 없을 땐 어떻게 해야할까? 아래 문제가 그런 문제다.

 

BOJ 1629번: 곱셈

1629번: 곱셈

b가 최대 21억 가까이 되기 때문에 a를 b번 곱하는 방식은 분명 시간 초과가 발생할 것이다. 더 효율적인 방법이 필요하다.

a^n × a^n = a^2n

12^58 === 4(mod 67) -> 12^116 === 16(mod 67)

12^58 과 12^116 의 관계에서 보듯 k승을 계산했으면 2k승을 계산할 수 있고, 2k승을 계산하고 a를 한 번만 곱해주면 2k+1승이 구해진다. 따라서 2k승과 2k+1승 모두 k승을 계산했으면 O(1)에 계산할 수 있다. 이처럼 a의 임의의 지수승을 귀납적으로 계산할 수 있다.

 

timeover version

#include <bits/stdc++.h>
using namespace std;

long long mul(long long a, long long b, long long c){
    long long ret = 1;
    while (b--) ret = ret * a % c;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int a,b,c;
    cin >> a >> b >> c;
    cout << mul(a,b,c);
    return 0;
}

answer

#include <bits/stdc++.h>
using namespace std;

long long mul(long long a, long long b, long long c){
    if (b == 1) return a % c;
    long long ret = mul(a,b/2,c);
    ret = ret * ret % c;
    if (b%2) return ret * a % c;
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int a,b,c;
    cin >> a >> b >> c;
    cout << mul(a,b,c);
    return 0;
}

base condition - b = 1 일 때로 두고 a가 m보다 클 수 있어 a 대신 a%c 반환. b=0일 때로 두면 틀림.

 

재귀적으로 a^b/2 mod m을 계산해 ret에 대입하고 ret을 제곱한다. 만약 b가 7이면 b/2는 3이니 ret은 a^6 mod m의 값이 들어간다. 즉 b가 짝수이면 그냥 val의 값을 반환하면 되지만 b가 홀수이면 val에 a를 한 번 더 곱해서 반환해줘야 한다.

 

이 함수의 시간복잡도는 b가 계속 절반씩 깎이기 때문에 O(log b)다.

틀렸거나 시간 초과가 발생했다면 int overflow가 발생했거나, 함수 내에서 함수를 1번 부르는게 아니라 2번 불러서 시간복잡도가 O(log b)가 아닌 O(b)가 됐거나, base condition을 빼먹었거나 하는 이유 등을 짐작해볼 수 있다.

 

난 시간 초과가 발생했는데 long long으로 했었으니 int overflow는 아니었지만 base condition에서 문제가 있었다.

 

---

3. 연습 문제 2 - 하노이 탑

BOJ 11729번: 하노이 탑 이동 순서 문제

11729번: 하노이 탑 이동 순서

n-1개의 원판을 기둥 1에서 기둥 2로 옮긴다.

n번 원판을 기둥 1에서 기둥 3으로 옮긴다.

n-1개의 원판을 기둥 2에서 기둥 3으로 옮긴다.

->원판이 n-1개일 때 옮길 수 있으면 원판이 n개일 때도 옮길 수 있다.

 

원판이 1개일 때 원판을 내가 원하는 곳으로 옮길 수 있다.

원판이 k개일 때 옮길 수 있으면 원판이 k+1개일 때에도 옮길 수 있다.

 

1. 함수의 정의 

함수 정의 - 함수가 어떤 역할을 수행하는지, 어떤 인자를 받는지를 정하는 것

//void func(int n)	//원판 n개를 기둥 1에서 기둥 3으로 옮기는 방법을 출력하는 함수
void func(int a, int b, int n)	//원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수

 

2. base condition

if (n==1)cout << a << ' ' << b << '\n';

3. 재귀 식

func(a, 6-a-b, n-1);	//n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다.
cout << a << ' ' << b << '\n';	//n번 원판을 기둥 a에서 기둥 b로 옮긴다.
func(6-a-b, b, n-1);	//n-1개의 원판을 기둥 6-a-b에서 기둥 b로 옮긴다.

문제에서는 총 옮긴 횟수도 같이 물어본다. 원판 k개를 옮기기 위해 A번 이동이 필요했다고 하면 원판 k+1개를 옮길 때는 k개의 원판을 빈 곳으로 옮길 때 A번, k+1번 원판을 옮길 때 1번, k개의 원판을 다시 빈 곳에서 목적지로 옮길 때 A번이 필요하여 총 2A+1번 이동이 필요하다.

+) 초항이 1이기 때문에 이 수열의 일반항은 2^k-1이 된다.

 

#include <bits/stdc++.h>
using namespace std;
// void hanoiTower(int from, int to, int n){
//     if (n==1){
//         cout << from << ' ' << to << '\n';
//         return ;
//     }
//     hanoiTower(from, 6-from-to, n-1);
//     cout << from << ' ' << to << '\n';
//     hanoiTower(6-from-to,to,n-1);
// }

void hanoiTower3(int from, int by, int to, int n){
    if (n==1){
        cout << from << ' '<<to<<'\n';
        return ;
    }
    hanoiTower3(from, to, by, n-1);
    cout << from << ' ' << to << '\n';
    hanoiTower3(by, from, to, n-1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int k;
    cin >> k;
    // cout << pow(2,k)-1<<'\n'; // 입력 최대가 20인 pow 함수 특성 상 오차가 커져 답이 틀린다.
    cout << (int)pow(2,k)-1<<'\n';
    // hanoiTower(1,3,k);
    hanoiTower3(1,2,3,k);
    // cout << cnt;
    return 0;
}

---

4. 연습 문제 3 - Z

BOJ 1074번: Z

1074번: Z

1. 함수의 정의

int func(int n, int r, int c)	//2^n * 2^n 배열에서 (r,c)를 방문하는 순서를 반환하는 함수

2. base condition

if (n==0) return 0;

3. 재귀 식

return func(n-1, r, c);	//(r,c)가 1번 사각형일 때
return half*half + func(n-1, r, c-half);	//(r,c)가 2번 사각형일 때
return 2*half*half + func(n-1, r-half, c);	//(r,c)가 3번 사각형일 때
return 3*half*half + func(n-1, r-half, c-half);	//(r,c)가 4번 사각형일 때

 

#include <bits/stdc++.h>
using namespace std;

int func(int n, int r, int c){
    if (n==0) return 0;
    int half = pow(2, 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);
    }
    if (r>=half && c>=half){
        return 3*half*half + func(n-1, r-half,c-half);
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N,r,c;
    cin >> N>>r>>c;
    cout << func(N,r,c);

    return 0;
}

---

5. 응용 3 - 시작점이 두 종류일 때

BOJ 4179번 불!

4179번: 불!

#include <bits/stdc++.h>
using namespace std;
char board[1001][1001];
int distFire[1001][1001];
int distJH[1001][1001];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int r,c;
    string s;
    cin >> r >> c;
    for (int i = 0; i < r; i++){
        cin >> s;
        for (int j = 0; j < c; j++){
            board[i][j] = s[j];
            distFire[i][j] = -1;
            distJH[i][j] = -1;
        }
    }
    queue<pair<int, int>> jh;
    queue<pair<int,int>> queue;
    
    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++){
            if (board[i][j] == 'F'){
                queue.push({i, j});
                distFire[i][j] = 0;
            }
            if (board[i][j] == 'J'){
                jh.push({i,j});
                distJH[i][j] = 0;
            }
        }
    }

    while(!queue.empty()){
        pair<int, int> cur = queue.front();
        queue.pop();
        for (int i = 0;i<4;i++){
            int x = cur.first + dx[i];
            int y = cur.second + dy[i];
            if (x < 0 || x >= r || y < 0 || y >= c) continue;
            if (board[x][y] == '#' || distFire[x][y] >= 0) continue;
            queue.push({x,y});
            distFire[x][y] = distFire[cur.first][cur.second] + 1;
        }
    }
    while(!jh.empty()){
        pair<int, int> cur = jh.front();
        jh.pop();
        for (int i = 0; i < 4; i++){
            int x = cur.first + dx[i];
            int y = cur.second + dy[i];
            if (x < 0 || x >= r || y < 0 || y >= c){
                cout << distJH[cur.first][cur.second] + 1;
                return 0;
            }
            if (board[x][y] == '#' || distJH[x][y] >= 0) continue;
            if (distFire[x][y] != -1 && distFire[x][y] <= distJH[cur.first][cur.second] + 1) continue;
            jh.push({x,y});
            distJH[x][y] = distJH[cur.first][cur.second] + 1;
        }    
    }
    cout << "IMPOSSIBLE";
    return 0;
}

 

불에 대한 BFS와 지훈이에 대한 BFS를 모두 돌림으로서 해결이 가능하다. 먼저 지훈이는 신경쓰지 말고 불에 대한 BFS를 돌려서 미리 각 칸에 불이 전파되는 시간을 다 구해둔다. 그 다음에는 지훈이에 대한 BFS를 돌리며 지훈이를 이동시킨다. 이 때 만약 지훈이가 특정 칸을 x시간에 최초로 방문했는데 그 칸에 x시간이나 그 이전에 불이 붙는다면 그 칸을 못가게 처리하면 된다.

원래 BFS의 구현에서는 방문했는지 여부를 vis[x][y]가 true인지 혹은 dist[x][y]가 0 이상인지 확인하고, 이미 방문한 칸이라면 continue를 한다. 하지만 이 문제에서는 추가로 해당 칸에 불이 붙은 시간을 확인해서 필요에 따라 continue를 하면 된다. 

 

불에 대한 BFS가 끝나고 나면 distFire에는 해당 지점에 불이 언제 붙는지가 저장된다. 지금까지의 BFS에서는 목적지가 정해져있거나 더 이상 갈 곳이 없을 때까지 계속 돌리는 상황이었던 반면 이번에는 외곽으로 탈출을 해야한다. (x, y)가 범위를 벗어났다는건 곧 탈출에 성공했다는 의미이고, 큐에 원소들은 거리 순으로 들어가기 때문에 최초로 탈출한 시간을 바로 출력하고 종료하면 된다.

 

시작점이 두 종류인 문제에 관해서 추가로 생각해야 할 점이 있다. 지금은 지훈이의 이동은 불의 전파에 영향을 받지만 불의 전파는 지훈이의 이동에 영향을 받지 않아서 불만 먼저 전파를 쭉 시키는게 가능했다. 그런데 시작점이 A, B 두 종류가 있고, A의 전파에 B가 영향을 주고 B의 전파에도 A가 영향을 준다고 하면 어느 하나를 먼저 끝까지 전파시키는게 불가능하다.

 

바킹독이 출제했던 18809번 문제가 딱 그런 문제로, 백트래킹 기법을 추가로 알고 있어야 해결이 가능하다. 두 종류의 BFS에서 BFS를 돌 때 어느 하나가 독립적이지 않고 서로에게 영향을 준다면 여기서 사용한 방법으로는 해결할 수 없다는 것을 꼭 이해해야 한다. 그런 상황에서는 시간 순으로 A와 B를 동시에 진행시켜야 한다.

18809번: Gaaaaaaaaaarden

 

---

6. 응용 4 - 1차원에서의 BFS

BOJ 1697번 숨바꼭질

1697번: 숨바꼭질

이차원에서의 BFS를 생각하면 상하좌우로 뻗어나가는 방식으로 진행이 됐는데 이건 전파가 상하좌우로 이루어졌기 때문이다.

이 문제에서도 수빈이가 X에 있다고 할 때 X-1, X+1, 2X로 이동하는 것을 BFS로 처리할 수 있다.

 

그런데 BFS의 범위를 어디까지로 해야할까? 0부터 100,000으로 하면 되는거 아닌가하고 쉽게 생각할 수 있지만, 문제를 보면 수빈이와 동생의 위치가 0에서 100,000 사이라고 했지 수빈이가 이동 중에 반드시 0에서 100,000 사이에만 있어야한다는 조건은 없다. 예를 들어 100,000 밖으로 나갔다가 다시 안으로 올 수도 있다.

 

일단 상식적으로 생각했을 때 음수로 갈 일은 없다. 가장 빠른 경로가 될 수 없기 때문이다. 그리고 100,000 바깥으로 나갈 수 있겠지만 일단 한 번 나갔다면 그 이후로는 -1만 계속 하게 되므로 동생을 가장 빠르게 찾아나가는 상황에서는 아무리 멀리가도 200,000을 넘어가지는 않는다.

 

따라서 0에서 200,000 사이에서만 BFS를 돌려도 답을 구하는데는 문제가 없으며 여기서 더 깊게 생각을 해보면 사실 100,000을 나가는 것 자체가 손해라는 것을 알 수 있다. +1로 100,000을 탈출하는건 비효율적이며, x2로 100,000을 탈출하는 상황이 있을 순 있겠지만, x2를 한 후 -1을 여러번 할 바에야 -1을 먼저 하고 x2를 하는게 더 낫기 때문이다.

 

위의 논리적인 과정을 거쳐 0에서 100,000 사이에서 움직인다고 가정한 것이지, 위의 과정 없이 당연히 수빈이가 0에서 100,000 사이에서만 움직인다고 멋대로 가정을 하고 풀면 안된다. 이 문제에서는 운 좋게 논리적으로 생각을 했을 때 수빈이가 0에서 100,000 사이에서만 움직이게 되었지만 다른 문제에서는 멋대로 가정한 것 때문에 전혀 다른 답이 나올 수 있다.

#include <bits/stdc++.h>
using namespace std;
// int board[100001];
int dist[100001];
int dx[3] = {1, -1, 2};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    // board[n] = 1;
    // board[k] = 1;
    for (int i = 0;i<100002;i++){
        dist[i] = -1;
    }
    dist[n] = 0;

    queue<int> queue;
    queue.push(n);
    while (!queue.empty()){
        int cur = queue.front();
        queue.pop();
        for(int i = 0;i<3;i++){
            int x;
            if (i==2){
                x = cur * dx[i];
            }else{
                x = cur + dx[i];
            }
            if (x < 0 || x > 100001) continue;
            if (dist[x] >= 0) continue;
            dist[x] = dist[cur] + 1;

            queue.push(x);
            // board[x] = 1;
        }
    }
    cout << dist[k];

    return 0;
}

---

참고자료

[실전 알고리즘] 0x0B강 - 재귀

[실전 알고리즘] 0x0B강 - 재귀