재귀

24 Dec 2023 in Posts on Algo, CPP

“0x0B강 - 재귀”

재귀

재귀

워크북

분류	백준 번호	문제 제목
연습 문제	1629	곱셈
연습 문제	11729	하노이 탑 이동 순서
연습 문제	1074	Z
기본 문제✔	17478	재귀함수가 뭔가요?
기본 문제✔	1780	종이의 개수
기본 문제✔	2630	색종이 만들기
기본 문제✔	1992	쿼드트리
기본 문제✔	2447	별 찍기 - 10
기본 문제✔	2448	별 찍기 - 11

많은 생각이 드는 주제

BOJ 1629 (곱셈)

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

int A, B, C;

long long   ppow(long long a, long long b, long long m)
{
    if (b == 0)
        return 1;
    if (b == 1)
        return (a % m);
    long long val = ppow(a, b / 2, m);
    val = val * val % m;
    if (b % 2 == 0)
        return val;
    return val * a % m;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> A >> B >> C;
    cout << ppow(A, B, C);
    return 0;
}

이런 문제가 재귀의 기본적인 연습 문제라는 것 부터가 상당한 진입장벽. 이 문제를 풀려면 거듭제곱의 분할 법칙에 대해 알아야만 한다. 예를 들어 7^5를 4로 나눈 나머지를 구하고 싶다면 어떻게 해야할까?
7^5를 4로 나눈 나머지는 7^2를 4로 나눈 나머지에 7^3를 4로 나눈 나머지를 곱한 값을 다시 4로 나눈 나머지와 동일하다. 즉 a^b를 c로 나눈 나머지는 …

\[((a^{\frac{b}{2}} \mod c) \cdot (a^{\frac{b}{2}} \mod c)) \mod c\]

와 동일하다는 것. 만약 b가 홀수라면 항 하나에 a를 한번 더 곱해서 계산(a^(b/2 + 1) mod c)한다.

위 원칙을 알면 함수를 만들어낼 수 있다.

// ...
    if (b == 0)
        return 1;

    if (b == 1)
        return (a % m);
// ...

종료 조건이다. 0승은 1이니까 무조건 1을 반환하고, 1승은 a 자신이므로 a % m을 반환한다.

long long val = ppow(a, b / 2, m);

val = val * val % m;

제일 제일 제일 제일 중요한 부분이다. 위에서 상술한 수식이 그대로 적용된 부분이다. val은 a^(b/2) % c를 나타내고, val = val * val % m;은 위 식을 그냥 그대로 받아적은 것이다. long long val = ppow(a, b / 2, m);에서 b는 계속 2로 나누어져 결국 1까지 떨어지게 되고 a % m을 반환한 후, 바로 위 재귀 단계에서부터는(2 혹은 3) val = val * val % m;을 거쳐가며 합쳐진다.

    if (b % 2 == 0)
        return val;

    return val * a % m;

이때 b가 짝수라면 val을 그대로 반환하고 b가 홀수라면 a를 한번 더 곱한 뒤 그 나머지를 반환한다(a^(b/2 + 1) mod c).

BOJ 11729 (하노이 탑 이동 순서)

이 문제의 경우, 일단 지금은 그냥 풀이 과정을 외워두기로 했다. 1개의 원판을 옮길 수 있기 때문에 k개의 원판을 옮길 수도 있다는 것이 이 하노이 탑 이동의 핵심 컨셉트라고 한다.

BOJ 1074 (Z)

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

int solve(int N, int r, int c)
{
    if (N == 0)
        return 0;

    int half = pow(2, N - 1);

    if (r < half && c < half)
        return solve(N - 1, r, c);
    else if (r < half && c >= half)
        return half * half + solve(N - 1, r, c - half);
    else if (r >= half && c < half)
        return half * half * 2 + solve(N - 1, r - half, c);
    return half * half * 3 + solve(N - 1, r - half, c - half);
}

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

    cout << solve(N, r, c);

    return 0;
}

재귀 카테고리의 문제를 여러 개 풀어본 결과, 이 문제와 비슷한 문제가 상당히 많고 풀이 과정도 거의 동일하다. 나는 이 문제를 “색종이류 문제”라고 부르기로 했다. 정사각형의 보드가 주어지고 함수를 호출해 2분의 1 내지는 3분의 1을 해서 구획을 나누고, 그 구획에 대해 다시 함수를 호출하여 기저 조건까지 파고들어가는 문제이다.

(0, 0) 시작이기 때문에 정확한 좌표는 2^(N - 1) - 1이 맞다…

2, 3, 4 사분면을 체크한다는 것은 이미 이전 사분면을 모두 체크했다는 이야기이기 때문에 함수를 호출할 때 이전 사분면을 체크한 부분을 더해줘야 한다. 2 사분면은 half^2를 한 번, 3 사분면은 두 번, 4 사분면은 세 번 더한다.
그리고 각 함수의 호출에 대해, r과 c의 좌표를 당겨서 기준점을 2^N인 사각형이 아니라, 2^N-1인 사각형으로 만들어줘야 한다(말로 설명하기가 애매하다).

BOJ 1780 (종이의 개수)

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

int board[2200][2200];
int paper[3];

bool    check(int x, int y, int z)
{
    for (int i = x; i < x + z; i++)
        for (int j = y; j < y + z; j++)
            if (board[x][y] != board[i][j])
                return false;
    return true;
}

void    func(int x, int y, int N)
{
    if (check(x, y, N)) {
        paper[board[x][y] + 1] += 1;
        return ;
    }
    int z = N / 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            func(x + (i * z), y + (j * z), z);
}

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

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> board[i][j];

    func(0, 0, N);

    for (int i = 0; i < 3; i++)
        cout << paper[i] << '\n';

    return 0;
}

색종이류 문제다.

위와 같은 정사각형을 3 * 3등분하여 재귀를 돌리는 식이다. 아래 식을 기억해야 한다. 색종이류 문제는 생긴 것만 다르지, 무조건 아래 식을 써서 재귀를 돌게 되어 있다.

int z = N / 3;
for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
        func(x + (i * z), y + (j * z), z);

3등분해서 z = N / 3인거지, 위에 Z문제처럼 절반으로 나눈 문제였으면 z = N / 2고, i랑 j도 각각 2까지만 돌았을 것이다. 기저 조건은 문제에 제시된 대로 구현되었다.

BOJ 2630 (색종이 만들기)

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

int N;
int board[130][130];
int ans[2];

bool    check(int x, int y, int N)
{
    for (int i = x; i < x + N; i++)
        for (int j = y; j < y + N; j++)
            if (board[x][y] != board[i][j])
                return false;
    return true;
}

void    func(int x, int y, int N)
{
    if (check(x, y, N)) {
        ans[board[x][y]]++;
        return ;
    }
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            func(x + (i * N) / 2, y + (j * N) / 2, N / 2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> board[i][j];

    func(0, 0, N);
    for (int i = 0; i < 2; i++)
        cout << ans[i] << '\n';
    return 0;
}

재귀를 N / 2으로 도는 것만 제외하면, 바로 위의 종이의 개수 문제와 거의 동일한 문제.

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            func(x + (i * N) / 2, y + (j * N) / 2, N / 2);

빠지지 않는 이 반복문

BOJ 1992 (쿼드트리)

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

int N;
int board[70][70];

int check(int x, int y, int N)
{
    for (int i = x; i < x + N; i++)
        for (int j = y; j < y + N; j++)
            if (board[x][y] != board[i][j])
                return -1;
    return (board[x][y]);
}

void    func(int x, int y, int N)
{
    if (check(x, y, N) != -1) {
        cout << check(x, y, N);
        return ;
    }
    cout << "(";
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            func(x + (i * N) / 2, y + (j * N) / 2, N / 2);
    cout << ")";
}

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

    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < N; j++)
            board[i][j] = s[j] - '0';
    }

    func(0, 0, N);

    return 0;
}

출력에 조금 특이사항이 생긴 것 빼고는 무난한 색종이 문제.

BOJ 2447 (별 찍기 - 10)

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

void    solve(int x, int y, int n)
{
    if (n == 1) {
        board[x][y] = '*';
        return ;
    }

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i == 1 && j == 1)
                continue ;
            solve(x + (i * n) / 3, y + (j * n) / 3 , n / 3);
        }
    }
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            board[i][j] = ' ';
        }
    }

    solve(0, 0, N);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << board[i][j];
        }
        cout << '\n';
    }

    return 0;
}

색종이류 문제는 아닌데, 까보면 색종이 문제의 냄새가 나는 별 찍기 10이다. 나머지가 1인 구간을 비우면 되는데, 따로 식을 세울 필요 없이 i와 j가 1인 부분만 건너뛰면 된다. i와 j가 나머지로 사용될 수 있다는 사실은 코드를 받아적으면서 깨달은 사실이다. N / 3의 색종이 반복문을 돌리면서 i와 j가 1일때만 걸러주면 되는 것이다. 이런걸 보자마자 알려면 얼마나 더 공부해야하는걸까…

BOJ 2448 (별 찍기 - 11)

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

int     N;
char    board[3100][6200];

void    solve(int x, int y, int n)
{
    if (n == 3) {
        board[x][y] = '*';
        board[x + 1][y - 1] = '*';
        board[x + 1][y + 1] = '*';
        for (int j = y - 2; j <= y + 2; j++)
            board[x + 2][j] = '*';
        return ;
    }
    solve(x, y, n / 2);
    solve(x + n / 2, y - n / 2, n / 2);
    solve(x + n / 2, y + n / 2, n / 2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 2 * N; j++)
            board[i][j] = ' ';
    }

    solve(0, N - 1, N);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 2 * N - 1; j++) {
            cout << board[i][j];
        }
        cout << '\n';
    }

    return 0;
}

단순한 색종이 문제보다 재귀 지점 찾는게 어렵다. 경험을 많이 쌓아봐야 하는걸까?

재귀

재귀

워크북