close
프로필 사진

6kittylog

github: @6kitty
coding/바킹독 · 2026. 2. 22. fullscreen 넓게보기

바킹독의 실전 알고리즘 : 재귀

바킹독의 실전 알고리즘 : 재귀

재귀 : 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘 (recursion)

N부터 1까지 출력하는 함수

int print_n(int n){
    if(n==0) return 0;
    cout<<n;
    return print_n(n-1);
}

int main(void){
    print_n(n);
}

1부터 N까지의 합을 구하는 함수

int sum_n(int n, int sum){
    if(n==0) return sum;
    return sum_n(n-1,sum+n);
}
int main(void){
    int sum=0;
    cout<<sum_n(n,sum);
}

더 직관적인 재귀는 아래와 같다. 

int sum_n(int n) {
    if (n == 1) return 1;
    return n + sum_n(n - 1); // n 더하기 (1부터 n-1까지의 합)
}

물론 sum은 그냥 수열 공식으로 쓰는 것이 좋다. -> {n(n+1)}/2

재귀 함수의 조건

void func1(int n){
    if(n==0) return 0; // 특정 조건에는 종료 (base condition)
    cout<<n<<' ';
    func1(n-1);
}

결국에는 base condition으로 수렴해야 한다. 이렇지 않으면 무한루프가 될 수 있다.

그리고 재귀는 코드가 간결하지만 메모리/시간이 많이 소모된다. 모든 재귀 함수는 재귀 구조 없이 반복문으로 만들 수 있다. 재귀 없이 구현했을 때 너무 복잡해지는 경우는 재귀로 구현하는 것이 좋다.

  1. 함수의 정의
  2. base condition
  3. recursion 식

연습 문제 1 : 1629번 곱셈

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

ll pow_recur(ll a, ll b, ll m){
    if(b==1) return a%m; //b가 1이면 그냥 본인만 
    ll val= pow_recur(a,b/2,m); //b/2로 재귀 호출 
    val=val*val%m; //반절 나눈 지수대로 val*val -> 지수 2n
    if(b%2==0) return val; //짝수이면 그대로 반환 
    return val*a%m; // b가 홀수이면 한 번 더 곱해서(2n+1) 반환 
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll a,b,c;
    cin>>a>>b>>c;
    cout<<pow_recur(a,b,c);
}

위 코드에서 pow_recur 함수가 a^b mod m을 계산해주는 함수이다. 이전 내용에서 재귀 함수에서 정의해야 되는 부분은 아래와 같았다.

  1. 함수의 정의 -> a의 b제곱을 계산해주는 함수(mod m 상황에서)
  2. base condition -> b가 1이면 본인 호출 a의 1승은 a이므로.
  3. recursion 식 ->

바킹독에서 하는 말이, 절차지향적 사고 대신 귀납적인 사고로 코드를 이해하라고 한다.

  1. base condition 잘 잡고
  2. k승의 결과를 토대로
  3. 2k, 2k+1승의 결과도 계산 가능하니
    재귀가 가능하다..고 함수를 이해할 필요가 있다고 한다(모르겠다........)

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

연습 문제 2 : 11729번 하노이 탑 이동 순서

  1. base condition 잘 잡고 -> 2번에 n이 1개일 때

  2. k의 결과를 토대로 -> n-1개는 2번에 가있고 n은 1에서 3으로

  3. 2k, 2k+1의 결과도 계산 가능하니 ->

  4. n-1개의 원판을 1에서 2로 옮기면

  5. n번째 원판을 1에서 3으로 옮길 수 있고

  6. 나머지 n-1개의 원판을 2에서 3으로 옮기면 된다

  7. 그러면 base conditon은 2(1도 가능은 함)

int N,K;

void move_recur(int n){
    if(n==1){
        cout<<"1 3\n";
        return;
    }
    //n-1개의 원판을 1에서 2로 옮기기 
    move_recur(n-1);
    cout<<"1 2\n";
    cout<<"1 3\n";
    cout<<"2 3\n";
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>N;
    K=(N-1)*3+1;
    cout<<K<<'\n';
    move_recur(N);
}

일단 이렇게 짜다가 끝났는데 함수 하나로는 안되고 각 출력마다의 func을 두어야 할 거 같긴 하다. 그냥 해설 보자..ㅜㅜ

  1. 함수의 정의

    여기서도 func(int n)은 적절하지 않다고 한다. func(int a, int b, int n)로 두어서 원판 n개를 a에서 b로 두는 방법을 출력하는 함수로 두어야 한다.

일단 여기까지만 하고 다시 내가 짜보자. 

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

/*
1. n-1개의 원판을 1에서 2로 옮기면 
2. n번째 원판을 1에서 3으로 옮길 수 있고 
3. 나머지 n-1개의 원판을 2에서 3으로 옮기면 된다 
4. 그러면 base conditon은 2(1도 가능은 함)
*/

int N,K;

void move_recur(int a, int b, int n){
    if(n==1){
        cout<<a<<' '<<b<<'\n';
        return;
    }

    //n-1개를 b에서 b+1로 옮기기 
    move_recur(a,6-a-b,n-1); 
    cout<<a<<' '<<b<<'\n';
    move_recur(6-a-b,b,n-1); 
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>N;
    K=(1<<N)-1; //-> 이건 대입으로 찾는 게 나을듯 (하노이는 2^n-1 외우기)
    cout<<K<<'\n';
    move_recur(1,3,N);
}

위와 같이 작성했더니 풀렸다.

  1. base condition

    위 코드와 같이 n==1이 맞았다. 근데 n==0일 때 코드가 더 예쁘게 완성된다고 한다.

  2. 재귀 식

    한가지 주의할 점이 처음에는 % 이용해서 기둥 1,2,3을 표현하려고 했었는데 나머지에 0도 있다는 것을 까먹고 있었다. 또한, 여기서는 1,2,3기둥이 순환한다는 보장이 없고 "남은" 기둥을 써야한다는 점이 중요하기에 1,2,3의 총합인 6에서 a기둥과 b기둥을 빼주는 것이 중요하다.

연습 문제 3 : 1074번 Z

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int N,r,c;

int cnt;
pair<int,int> cur;

void vis_recur(int a,pair<int,int> n){
    /*
    1. 함수 정의 -> 2의 a승일 때 호출, 좌표와 함께
    2. base condition -> 좌표 간 2^1일 때 
    3. 재귀 호출 
    */

    //이때 n은 맨끝 좌표 
    if(a==1){
        if(cur.X-1==r&&cur.Y-1==c) cout<<cnt+1; else cnt++;
        if(cur.X==r&&cur.Y-1==c) cout<<cnt+1; else cnt++;
        if(cur.X-1==r&&cur.Y==c) cout<<cnt+1; else cnt++;
        if(cur.X==r&&cur.Y==c) cout<<cnt+1; else cnt++;
        return;
    }

    vis_recur(a-1,{(cur.X)/2,(cur.Y)/2});
    vis_recur(a-1,{(cur.X),(cur.Y)/2});
    vis_recur(a-1,{(cur.X)/2,(cur.Y)});
    vis_recur(a-1,{(cur.X),(cur.Y)});
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>N>>r>>c;
    vis_recur(N,{1<<N,1<<N});
}

제미나이 채점 돌려보니까 논리는 맞는데 전체 판을 다 돌리면 시간 초과가 발생한다고 한다. 바킹독으로 돌아가서 풀이 확인해보자.

바킹독에서는 재귀 함수를 아래와 같이 정의했다.

  1. 함수의 정의 -> func(int n, int r, int c)

    (r,c)를 방문하는 순서를 반환하는 함수

  2. base condition

    n=0일 때 return 0;

  3. 재귀 식

    사분면으로 나누어서 func(n-1,r,c), half*half+func(n-1,r,c-half) 이런 식으로...

여기서 half는? 사분면의 반절 쪼개서 그 넓이. 그 넓이는 이미 순회를 했을 테니까 더해주는 것이다. 다시 정리하자면...

  1. (r,c)가 1사분면에 있을 떄 -> return func(n-1,r,c);
  2. (r,c)가 2사분면에 있을 때 -> half*half+func(n-1,r,c-half);
  3. (r,c)가 3사분면에 있을 때 -> 2halfhalf+func(n-1,r-half,c);
  4. (r,c)가 4사분면에 있을 때 -> 3halfhalf+func(n-1,r-half,c-half);

잠깐. 좌표에서는 왜 half를 빼주는지 생각해보자. 아, 다른 사분면은 더해주고 다시 그 작은 정사각형에서의 좌표가 리셋되기 때문이다. 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int N,r,c;

int cnt;
pair<int,int> cur;

int vis_recur(int n,int a, int b){
    if(n==0) return 0;
    int half=1<<(n-1); //2의 (n-1)승 
    if(a<half && b<half) return vis_recur(n-1,a,b); //1사분면 
    if(a<half && b>=half) return half*half+vis_recur(n-1,a,b-half);
    if(a>=half && b<half) return 2*half*half+vis_recur(n-1,a-half,b);
    if(a>=half && b>=half) return 3*half*half+ vis_recur(n-1,a-half,b-half);
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>N>>r>>c;
    cout<<vis_recur(N,r,c);
}

최종본이다. 재귀를 잘 이해한 뒤에 백트래킹을 듣는 게 좋다고 한다(미리 알았더라면 벼락치기 하지 않았을 텐데..)

'coding > 바킹독' 카테고리의 다른 글

바킹독의 실전 알고리즘 : DFS  (0) 2026.02.22
바킹독의 실전 알고리즘 : BFS  (1) 2026.02.16
바킹독의 실전 알고리즘 : 스택의 활용(수식의 괄호 쌍)  (0) 2026.02.15
바킹독의 실전 알고리즘 : 덱  (0) 2026.02.15
바킹독의 실전 알고리즘 : 큐  (0) 2026.02.15
coding/바킹독 관련 글
더 보기
Copyright © 육키티 모든 권리 보유.
SKIN: Copyright © 쭈미로운 생활 All rights reserved. Designed by JJuum.
and Current skin "dev-roo" is modified by Jin.

티스토리툴바