컴공댕이 공부일지
[실전 알고리즘] 0x0B강 | 재귀 (Recursion) - 이론부터 예제 문제풀이까지, 재귀 문제의 구조 완벽 익히기 😎 본문
[실전 알고리즘] 0x0B강 | 재귀 (Recursion) - 이론부터 예제 문제풀이까지, 재귀 문제의 구조 완벽 익히기 😎
은솜솜솜 2025. 3. 21. 03:40
🔎 재귀(Recursion)란?
하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘.
재귀가 낯설고 어렵게 느껴지는 이유는 우리가 기존에 생각하던 "절차지향적 사고"를 탈피해야하기 때문.
절차 지향적 사고 vs 귀납적 사고
도미노로 예시를 들면,
- 절차 지향적 사고
1번 도미노, 2번째 도미노, 3번째 도미노 ... 이렇게 순차적으로 쓰러져서 모든 도미노가 쓰러진다 !
=> (각 단계가 순차적으로 실행)
- 귀납적 사고
- 1번 도미노가 쓰러진다.
- k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.
=> 모든 도미노가 쓰러진다 ! 는 결론에 도달.
이번 글에서는 바킹독 선생님의 강의를 기반으로, 재귀의 기본 개념을 정리하고, 예제 문제를 풀이해볼 것이다.
📝 재귀 함수의 조건
특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함 (Base condition)
그리고 모든 입력은 base condition으로 수렴해야 함
한마디로 종료 조건이 꼭 있어야 하고, 모든 입력은 다 종료 조건으로 향해 가야만 한다 ㅇㅇ
(아니면 무한루프에 빠져효 ,,)
📌 tips ; 재귀 더 자세히 알아보기
1️⃣ 명확히 정의하기 (전달받을 인자, 어디까지 계산하고 넘길지)
2️⃣ 모든 재귀는 반복문으로 동일한 동작하는 함수 만들 수 있다 !
🔎 재귀 vs 반복문
코드가 자연스레 재귀적일 때 (트리 탐색, 분할 정복)
재귀 없이 구현을 하면 코드가 너무 복잡해질 때는 재귀로 구현을 하는게 좋다.
반면 반복문으로 간결하게 해결할 수 있고, 성능이 중요한 경우 반복문 사용이 낫다.
재귀는 코드는 간결해보여도 함수 호출에 큰 비용이 들기 때문에 메모리와 시간은 손해 !
문제들을 풀다보면 경험적으로 어떤 때 재귀를 사용하는 게 유리하고, 혹은 사용할 필요가 없는지 알게된다고 함 ㅇㅇ
3️⃣ 자기 자신 여러 번 호출하면, 비효율적일 수 있다
ex) 피보나치. 계산한 것을 중복해서 재차 계산하므로 n이 커질수록 비효율적 ..
4️⃣ 재귀함수가 자기 자신 부르면, 스택 영역에 계속 누적 된다
스택 메모리엔 지역 변수, 함수 호출 정보 등등이 쌓인다. 너무 많은 재귀 호출이나 큰 지역변수를 사용하면 스택 오버플로우가 발생한다. 그래서 너무 깊은 재귀를 써서 여러번 호출해버리면,, 런타임 에러가 난다. 그러니 재귀 깊게 들어가는 풀이는 반복문으로 문제 풀쟈 !
📝 문제 유형 1) 거듭제곱
백준 1629번 곱셈 (https://www.acmicpc.net/problem/1629)
- a를 b번 곱한 수를 c로 나눈 나머지 구하는 문제 ! 아래 코드는 바킹독 스승님 코드입니닷
// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/a9f89b45ac624c2a8d13f27a01dd78d1
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll POW(ll a, ll b, ll m){
if(b==1) return a % m;
ll val = POW(a, b/2, m);
val = val * val % m;
if(b%2 == 0) return val;
return val * a % m;
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
ll a,b,c;
cin >> a >> b >> c;
cout << POW(a,b,c);
}
b가 절반씩 깎여서 1이 될 때 끝나니까, 시간 복잡도는 O(log b)다.
바로바로 리턴해버리구 세상 깔-끔한 풀이.. 뭔가 풀이 자체는 똑같은데도 뭔가 구냥 선생님께 더 깔끔해보이는 것 같움 . . .
잘 써진 문구가 있어 선생님 말씀을 그대로 인용합니다 ~
이렇게 재귀 함수를 만들어낼 수 있고 꼭 절차지향적인 사고 대신 귀납적인 사고로 이 코드가 올바른 답을 낸다는 사실을 이해하면 좋겠습니다. 물론 이 문제까지는 예를 들어 POW(5, 14, 3)이 POW(5, 7, 3)을 부르고, POW(5, 7, 3)이 POW(5, 3, 3)을 부르고 이런식으로 절차지향적인 사고로 따라가는게 어렵지 않지만 점점 그렇게 따라들어가려고 하면 머릿속이 너무 복잡해질 문제들을 만나게 될 것입니다.
그 때 재귀 함수를 잘 짜려면 귀납적인 사고, 즉 base condition을 잘 잡아뒀고, k승의 결과를 토대로 2k, 2k+1승의 결과를 계산할 수 있으니 마치 도미노를 쓰러트리는 것 처럼 모든 결과가 잘 계산될 것이다로 함수를 이해할 필요가 있습니다.
움 사실 뭔가 아직은 .. 쪼오끔 재귀가 잘 와닿지 않고 안붙는 느낌 . . ㅠ 귀납적 사고 어렵네여.. 암튼 스승님 말씀대로 k승이 계산 가능하니, 2k, 2k+1(홀수)도 구할 수 있다 ! 그래서 11승을 5승 6승으로 나눠 계산하고 이렇게 쪼개고 쪼개서 다 계산할 수 있다 ! 라는게 결론. 아 어렵따 구현, PS 많이많이 해봐야겟다 .. . .
번외 ) trouble shooting
1트 - 시간초과
11제곱을 계산하려면, 5승 * 6승 이렇게 풀이하려 했더니 .. 중복계산이 넘 많아서 오류나벌임~ b를 기껏 반으로 쪼개놓고.... 최종적으로 2번 호출해버리니 .. 그냥 그대로 O(b)거덩요 ~ ^^ㅠ
그래서 좀 고민해봤더니.. 그냥 반띵만 계산하고 홀수인 경우에 한 번만 더 곱하면 되더라구요 ?~?
그래서 2트 바로 도전.
int recursion(int a, int b, int c) {
if(b==0) return 1; // 0승은 1
else if(b==1) return a%c; // 1승이면 그냥 a
return ( recursion(a, b/2, c)%c ) * ( recursion(a, b-b/2, c)%c ) %c;
}
2트 - 오버플로우
int 타입으로 냅다 해버려서.. 최종 mod 연산하면 int안으로 들어오긴 하는데.. 계산 과정 중간중간 int 범위를 넘게되고 그래서 오버플로우가 나서 틀림 ! 그래서 long long 타입으로 싹 바꾸고 3트 ~
int recursion(int a, int b, int c) {
if(b==0) return 1; // 0승은 1
else if(b==1) return a%c; // 1승이면 그냥 a
int half = recursion(a, b/2, c);
half = (half*half) %c;
if(b%2) half = (half*a) %c; // b가 홀수면 a 한 번 더 곱하기
return half;
}
3트 ~ 최종 제출 코드. 성공 !
#include <iostream>
using namespace std;
typedef long long ll;
int recursion(ll a, ll b, ll c) {
if(b==0) return 1; // 0승은 1
else if(b==1) return a%c; // 1승이면 그냥 a
ll half = recursion(a, b/2, c);
half = (half*half) %c;
if(b%2) half = (half*a) %c; // b가 홀수면 a 한 번 더 곱하기
return half;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
ll a, b, c;
cin >> a >> b >> c;
cout << recursion(a, b, c);
return 0;
}
+ 4트. 조금 더 정리한 최종 ver.. 0일 때의 base condition은 사실 필요가 없거덩 b=1인 순간에 어차피 리턴돼서 ㅇㅇ
int rec(ll a, ll b, ll c) {
if(b==1) return a%c;
ll half = rec(a, b/2, c);
ll ans = half*half%c;
if(b%2) return ans*a%c;
else return ans;
}
문제 다 풀고 강의보는데 '만약 직접 짜서 냈는데 틀렸거나 시간 초과가 발생했다면 int overflow가 발생했거나, POW 함수 내에서 POW 함수를 1번 부르는게 아니라 2번 불러서 시간복잡도가 O(log b)가 아닌 O(b)가 됐거나, base condition을 빼먹었거나 하는 이유 등을 짐작해볼 수 있습니다.' 라고 하셔서... 너무 소름돋음 ㅋㅋㅋㅋㅋ ㅜ 정확히 예상을 빗나가지 않고 . . .오버플로우 나서 틀리고, 반띵한 결과 각각 재귀호출해서 2번씩 호출해버려서 틀렷는데 . . .ㅠ 더 열심히 집중하쟈 . .....
📝 문제 유형 2) 하노이 탑
백준 11729번 하노이 탑 이동 순서 (https://www.acmicpc.net/problem/11729)
- 하노이탑 구현해 수행 과정을 출력하고, 최소 이동 횟수 구하는 문제
보통 재귀에서 수열 일반항 구해 수행 횟수 구하는 건 거의 안물어본대. 하노이탑은 워낙 유명해서 물어보는거라구 ㅇㅇ..
#include <iostream>
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); // a에 있던 n-1 원판들을 빈 기둥으로
cout << a << " " << b << '\n'; // a에서 b로 n번째 원판 옮김.
func(6-a-b, b, n-1); // 빈 기둥에 있던 원판들을 b로
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
cout << (1<<n)-1 << '\n'; // 일반항 : 2의 n승 -1
func(1, 3, n);
return 0;
}
보다 작은 원판만 위로 쌓을 수 있음 ..!
고로 n 까지의 원판을 3번째 기둥으로 다 옮기려면, n보다 작은 n-1번까지는 2번째 기둥에 모두 쌓여야함.
그리고 2번째 기둥의 n-1개의 원판을 3번째 기둥에 위치한 n번째 원판 위로 쌓기만 하면 됨.
즉, 1개짜리 원판도 처리가 가능하고,
n-1개의 원판을 내가 원하는 기둥으로 옮길 수만 있다면, n개의 원판도 처리할 수 있다
=> 재귀 !! (k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.)
본격 구현 과정.
기둥 a에서 기둥 b로 n개의 원판을 옮기는 과정을 출력할 함수 func(int a, int b, int n)
여기서 각 기둥은 1, 2, 3번이고,
먼저 n-1개의 원판을 출발지 a와 도착지 b를 제외한 나머지 하나의 기둥에 쌓아야한다.
그리고 n번째 원판을 출발지 a에서 도착지 b로 옮기고,
a도 b도 아닌 기둥에 있던 n-1개의 원판들을 도착지 b의 n번째 원판 위에 옮기기만 하면 끗!
세 기둥 1,2,3을 더하면 6이고, a + b + 나머지 기둥 = 6이 되어야하므로 나머지기둥은 6-a-b로 정의된다.
즉, 정리하자면 ~
1. 위에 있는 n-1개 원판을 빈 기둥으로 옮긴다.
2. 가장 큰 원판을 목적지로 옮긴다.
3. 빈 기둥에 있던 n-1개 원판을 다시 목적지로 옮긴다.
이 패턴이 반복 !!
사실 ... 코드 못 짜겠어서 선생님 코드 봤어욯 .. 보고도 약간 이해안되는데 그래도 n에 1, 2, 3 순차적으로 넣어보고 하노이탑 그려보면서 약간 왜 재귀인가..는 감이 왔음 ㅇㅇ 그렇게 찜찜하게 마저 강의를 틀어보는데 바로 딱 내 생각 읽은듯 얘기하셔서 소름ㅎ.. 재귀적 사고 으렵네여 ,,,,,,,,,, 뇌가 뒤틀리구잇음 ^^,,ㅠ
📝 문제 유형 3) Z
백준 1074번 Z (https://www.acmicpc.net/problem/1074)
사실 처음에는 저 방식대로 칸을 순회하면서 다 카운트 해야하나.. 이차원 배열을 만들어야하나.. 감도 안왔는데ㅎ 선생님의 도입 힌트를 보고 나서 풀었다.
해당 그림은 n=3인 경우의 그림이다. 8X8칸을 빨간 선으로 4분면으로 나눠보았다 각 사분면에 같은 색으로 동글동글 칠해놓은 애들을 주목하자! 사분면을 기준으로 동일한 지점에 위치하는 요 동글동글 친구들은 이동 횟수에 규칙이 보인다 ! 파랑이에 16칸 더하면 보라색이고, 마찬가지로 보라색에 16칸 더하면 빨강, 거기에 +16칸하면 노랑이 된다. 당연하면서도 새로운 발견이다 !!
여기서 재귀식이 나온다.
(몇번째사분면인지) * ( 한 사분면의 칸 개수 ) + 1사분면(그림 속 파란색 동그라미)의 이동횟수
1사분면의 이동횟수를 구하기 위해 재귀적으로 쪼개고 쪼개야한다. 8X8, 4X4, 2X2, 그리구 마침내 1X1이 되었을 때 종료조건에 들어간다. 그리구 1사분면을 고대로 본떠 다른 사분면으로 움직인것이니, r과 c도 2^(n-1)로 나눈 나머지를 취한다.
이게 사실 나도 바로 뽑아낸 건 아니고, 한참 고민해도 길이 안보여서.. 바킹독 스승님이 알려주신 힌트 (각 사분면 동일지점들의 위치 규칙) 을 보고 n=3일때, n=2일때 하나하나 그려보고서 고민하고 얻어낸 식이닿ㅎ.. 힌트도 안보고 혼자 풀었다면 진지하게 n시간 걸렸을듯.
재귀식만 뽑아냈다면 코드는 매우매우 간단하다. 아래와 같다.
첫번째 풀이
#include <iostream>
#include <cmath>
using namespace std;
int func(int n, int r, int c) {
int x=0;
if(n==0) return 0;
// 몇 번째 사분면인지 체크 ; 4분면의 기준이 2의 n-1승.
int power = static_cast<int>(pow(2, n-1));
if(r<power && c>=power) x=1;
else if(r>=power && c<power) x=2;
else if(r>=power && c>=power) x=3;
return x*power*power + func(n-1, r%power, c%power);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL);
int n, r, c;
cin >> n >> r >> c;
cout << func(n, r, c);
return 0;
}
바로 맞았습니다를 받았당
다만 쪼끔 수정하면 좋을 부분들이 있는데,
1. pow 함수 대신 비트 연산(<<) 사용해 2의 제곱수 구하기
pow 함수로 제곱수를 구했더니, double 형으로 반환되어 형변환을 해줘야하기도 해서.. 깔끔하게 비트연산자를 사용해주었다. pow함수는 함수 호출이 필요하지만, 비트연산은 CPU 단에서 즉시 연산되어 빠르다고한다.
2. 사분면 분기 단순화
int quadrant = (r >= power) * 2 + (c >= power);각 분기별로 if 문을 걸어서 각 사분면이 몇번째인지 x에 저장하는 기존 방식 대신, 위와 같이 조건문 한 줄에서 x값을 바로 계산하는 방식이다. 이건 사실 지피티가 조언해준 방식인데 조금 직관성?은 떨어져도 코드는 간결해서 한 번 써봤다.
개선된 풀이 :)
#include <iostream>
using namespace std;
int func(int n, int r, int c) {
if(n==0) return 0;
int power = 1 << (n - 1);
int quadrant = (r >= power) * 2 + (c >= power);
return quadrant*power*power + func(n-1, r%power, c%power);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(NULL);
int n, r, c;
cin >> n >> r >> c;
cout << func(n, r, c);
return 0;
}
마무리하며
재귀문제들 정말,, 코드는 진쨔 간단한데 받아들이기 쉽지 않았다. 절차지향적 사고에서 벗어나 n=1이 성립하고 && n=k, n=k+1이 성립하면 재귀다!! 라는 사고를 반복적으로 주입해주셨는데 감이 올랑말랑.. 어렵지만 문제 푸는 틀은 어느정도 받아들여진 것 같다.
재귀 문제 풀이의 틀을 마지막으로 정리하자면,
1. 함수의 구조 정의 (어떤 모양, 어떤 인자 받을지)
2. base condition (종료조건은 무엇인지)
3. 재귀 식 (최종 반환할. 재귀로 돌릴식이 무엇인지)
요 3단계로 구조화해서 재귀문제를 풀라구 스승님께서 말씀하셧사옵나이다 ~
음~ 새벽 3시 40분이다 ~
다행히도 내일 알바가 없어서.. 드디어 드디어 재귀 정리글을 마칠 수 있었다. 얼마만인지 ............. 거의 2월 말부터 써둔 글인데 이제서야 마무리가 된다...ㅎ ㅜ
매일 한 문제씩 쫌쫌따리 풀랬는데.. 이펍 세미나랑 스터디도 시작하고, 포스코 엔비전 보고서며 개강시즌 약속이며 알바며..ㅎㅎ 거기다 감기까지... (지금도 콜록거리고 있따) 여튼 이런저런 핑계거리들이 많았다 ㅎ.. 사실 다 핑계야 진짜. 여튼 좀 정신없이 바빴던 3월이었다~
Z문제를 풀자마자 이제 골드3이되었다. 백준 정말 오래했다고 생각했는데.. 이제 222문제 풀었단다. 이런....... 시간 여유 있는 요즘, 열심히 해야지😢 목표, 올해 끝날때까지 400문제 풀기~ 푸하하 올해 대략 285일남았는데 가능하지 않을까? (막이래
그래도 자바 공부나 다른 공부보다 코테공부가 쪨 재밌는 듯... 잔잔한 노래 하나 틀어두고, (오늘의 노래 추천 산들의 너는 계절처럼 멀어져가네) 어케 풀지 문제 째려보고 끄적거려보디보면 어느새 노래소리도 안들리는 무아지경(?)의 상태에 도달하게 되는데.. 그게 좋다. 다들 자는 가운데 나만 남은 .. 조용하고 평온한 이 새벽이 나는 참 조은 것 같다. 알바땜에 요새 못 즐기다가 알바없는날 오랜만에 새벽 공부 진득하게 즐겨보니 기분조타 히히..
마침 오늘 기학 팀플 언니들 만나서.. 저녁 시켜먹으면서 진로 얘기도 해서.. 개발 공부고 ai고 뭘 해야할지 도통 모르겠고 ... 취업이니 졸업이니 .... 멀게만 느껴지구 디게디게 막막한데 ,,,, 그래도 잠시 코테로 도피(?) 히히... 이제 알바도 좀 적응했겠다 다시 스트릭 꾸준히 이어봐야지 아자아자 ~! 아니 근데 월급날 언제죠? 지금 통장에 딱 7천원잇어요 으악
(출처) [실전 알고리즘] 0x0B강 - 재귀
[실전 알고리즘] 0x0B강 - 재귀
안녕하세요, 재귀 파트를 시작하겠습니다. 지금 자신있게 말할 수 있는게 있는데 이 파트가 정말 어려울 것입니다. 물론 이전의 내용들 중에서도 군데군데 어려운게 있었겠지만 이번 단원에서
blog.encrypted.gg
'PS > 알고리즘' 카테고리의 다른 글
| [실전 알고리즘] 0x0C강 | 백트래킹 (Backtracking) - 이론 & 예제문제 풀이 / next_permutation 함수의 활용 (0) | 2025.04.13 |
|---|---|
| [실전 알고리즘] 0x0A강 | 깊이 우선 탐색 (DFS) - 스택으로 DFS 구현하기 / DFS와 BFS의 차이? (0) | 2025.02.13 |
| [실전 알고리즘] 0x09강 | 너비 우선 탐색 (BFS) - 응용 문제 유형별로 풀어보기 📝 (0) | 2025.02.13 |
| [실전 알고리즘] 0x01강 - 🔎 정수 및 실수 자료형의 특징 / 2의 보수법 (0) | 2025.01.15 |
| [ 동적계획법 ] top-down, bottom up (상담시간 퇴사 문제) (0) | 2024.04.02 |
