0x0B강 - 재귀

알고리즘 설명

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

절차지향적사고를 버리고 수학적 귀납법으로 문제를 해결해야함

-재귀 함수의 조건

특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야함(Base condition)
모든 입력은 base condition으로 수렴해야 함

-재귀에 대한 정보 1

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

모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음

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

-재귀에 대한 정보 2

한 함수가 자기자신을 여러 번 호출하게 되면 비효율적일 수 있음

ex) 피보나치함수에대해 단순하게 구현을 한경우 자기자신을 계속해서 호출하기 때문에 O(1.1618 ^ N)이라는 매우 큰 시간 복잡도를 가지게됨

-재귀에 대한 정보 3

재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨

스택메모리가 제한되어있다면 재귀를 만번이상만 돌아도 런타임에러가 발생함

연습 문제 1 - 거듭제곱

a^B mod m

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

오버 플로우를 방지하기위해 long long 자료형을 사용

a를 곱해줄때마다 오버플로우 방지를 위해 m으로 나눠줌 -> 우리는 나머지를 구하고 싶은것이기 때문에

21232323 2334 의 1의 자리를 구할때 모든 자릿수를 계산하는것이 아닌 1의 자리만 곱해주는것과 같은 이치 그저 10이 m으로 바뀌었을뿐이다.

1629 . 곱셈

a^N * a^N = a^2N

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

1승을 계산할 수 있다.
K승을 계산했으면 2k승과 2k + 1승도 O(1)에 계산할 수 있다.

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


ll a, b, c;
ll func(ll a, ll b)
{
	if (b == 0)
		return 1;
	if (b == 1)
		return a %c;
    //종료 조건을 설정
	if (b % 2 == 1)
		return func(a, b - 1) * a;
    // b가 홀수일경우 b-1을 해주고 a를 한번곱해줘서 b를짝수로만들어줌
	ll half = func(a, b / 2) % c;
    // K승을 구해서 곱해주면 2K승을 구할수있다
	return half * half % c;
	

}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> a >> b >> c;

	cout << func(a, b) % c << '\n';
    //함수를 호출해줌 결과값이 c보다 클수있기 때문에 %c
}

11729 . 하노이 탑

1. 함수의 정의

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

2. base condition

n= 1일 때 cout << a <<' '<< b << '\n';

3. 재귀식

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-n,b , n-1);

#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()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int k;
	cin >> k;

	cout << (1 << k) - 1 << '\n';
	func(1, 3, k);
}

절차지향적사고를 벗어나 수학적인 접근을 해야 문제를 이해할수있다.
판이 한개일 때 문제를 해결할수있고.
k개일때 k+1개일때 문제를 해결할수있다는것을 아이디어로 문제를 해결해야한다.

해설을 봐도 문제가 잘이해되지않았으나
https://www.youtube.com/watch?v=AogMbfRwguk
를보고 문제를 다시 이해해보니 조금더 이해가된거같다.

1074. z

#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()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n,r,c;
	cin >> n >> r >> c;

	cout << func(n,r,c) << '\n';
	
}

그칸의 번호는 내가 지나온 칸의 번호와 같다는 것을 아이디어로 문제를 해결한다.

사각형을 사등분하면 각 사각형의 한변은 은 현재 2^ n-1 이다 이를 제곱하면 한 사각형안의 들어있는 숫자이다 각 1,2,3,4 번쨰는 사각형은 그를 더해준만큼 넘어간것이다.

이를 통해 n이 0일될떄까지 그칸을 가기위해 넘은 숫자들을 더해주면 해당 칸의 번호를 알수있다.

17478 . 재귀함수가 뭔가요?

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

int n;
void func(int cnt)
{
	for (int i = 0; i < cnt; i++)
	{
		cout << "____";
	}
	cout << "\"재귀함수가 뭔가요?\"" << '\n';
	if (cnt == n)
	{
		for (int i = 0; i < cnt; i++)
		{
			cout << "____";
		}
		cout << "\"재귀함수는 자기 자신을 호출하는 함수라네\"" << '\n';
		for (int i = 0; i < cnt; i++)
		{
			cout << "____";
		}
		cout << "라고 답변하였지." << '\n';
		return;
	}
	for (int i = 0; i < cnt; i++)
	{
		cout << "____";
	}
	cout << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어." << '\n';
	for (int i = 0; i < cnt; i++)
	{
		cout << "____";
	}
	cout << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지." << '\n';
	for (int i = 0; i < cnt; i++)
	{
		cout << "____";
	}
	cout << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"" << '\n';
	func(cnt + 1);
	for (int i = 0; i < cnt; i++)
	{
		cout << "____";
	}
	cout << "라고 답변하였지." << '\n';




}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다." << '\n';
	func(0);
}

숫자를 입력받아 숫자 만큼 재귀를 통해 문자열을 출력하는 문제이다.
난 우선 숫자 n을 전역으로 선언해두고 입력을받았다.

다음 0부터 n까지 재귀함수를 호출하는 방식으로 문제를해결했다.(재귀함수의 인자 cnt를 0부터시작하고 n을 base condition으로 두는 방법으로)

우선 시작부분인 어느날한~ 부분을 출력해주고

func(0)을 호출한다.

모든 문자열 앞에서는 ____ 을 현재 cnt만큼 출력한다.

다음 재귀함수가 뭔가요까지 호출한다음 base condition을통해 마지막 문자열을 출력해주고 return을 통해 종료하면 끝이다.

"앞에는 \로 문자열의시작과끝이아닌 특수문자로 사용했음을 표시해야한다.

1780 . 종이의 개수

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

int n;

int board[2200][2200];

int arr[3];

void func(int n,int x,int y)
{
	if (n == 0)
		return;

	int number = board[x][y];
	for (int i = x; i < x+n; i++)
	{
		for (int j = y; j < y+n; j++)
		{
			if (number != board[i][j])
			{
				for (int nx = 0; nx < 3; nx++)
				{
					for (int ny = 0; ny < 3; ny++)
					{
						func(n / 3, x + (nx* n/3), y +(ny * n / 3));

					}
				}
				return;
			}
		}
	}

	arr[number + 1]++;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

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

	func(n,0,0);

	for (int ans : arr)
	{
		cout << ans << '\n';
	}
	
}

배열의 크기 n을 입력받고 배열을 입력받아 채워주다 정답은 arr배열에 -1,0,1의 수를 더해준다.

func함수는 n행렬의 한변의 길이 , x 행의 시작좌표 ,y 열의 시작좌표를 인자로 받고

n이 0일경우를 base condition으로 잡아둔다 하지만 n이 3으로 나눠지면서 1이될경우 어차피 칸의 크기가 1이고 한칸짜리 모두 크기가 같은 배열로 잡히기 떄문에 오류가 발생한경우가아니면 0이 될 일이없다.

다음 board[x][y]를 기준으로 잡고 x+n , y+n만큼 탐색하며 만약 반복문을 탈출한다면 그칸은 모두 같은값이니 arr배열에 값을 올려준다 (-1부터시작하니 1을 더해 배열의 인덱스로 사용한다)

만약 중간에 다른값이 나온경우 사각형을 9개로 나눈다 즉 n/3으로 나누고 각 9개의 사각형의 x,y좌표를 넣어줘서 func를 호출해준다.

함수가 종료되면 arr에 들어있는 값들을 출력한다.

1992 . 쿼드트리

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

int n;

int board[65][65];


void func(int n,int x,int y)
{
	if (n == 0)
		return;

	int number = board[x][y];
	for (int i = x; i < x+n; i++)
	{
		for (int j = y; j < y+n; j++)
		{
			if (number != board[i][j])
			{
				cout << '(';
				func(n / 2, x, y);
				func(n / 2, x, y + (n / 2));
				func(n / 2, x + (n/2), y);
				func(n / 2, x + (n / 2), y + (n / 2));
				cout << ')';
				return;
			}
		}
	}

	cout << number;
}

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

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < str.size(); j++)
		{
			board[i][j] = str[j] - '0';
		}
	}

	func(n, 0, 0);
}

이전 문제와 해결방식은 동일하다 하지만 값을 출력하는 부분에서 반복문을 탈출하는 경우는 number를 출력해주고 만약 중간에 다른값을 만난경우 ( )를 func를 호출하기 전과 후에 출력해주면 각 압축된값으로 출력이될것이다.

2447 . 별찍기 - 10

#include <iostream>
using namespace std;
void star(int i, int j, int num)
{
    if ((i / num) % 3 == 1 && (j / num) % 3 == 1) {
        cout << ' ';
    }
    else
    {
        if (num / 3 == 0)
            cout << '*';
        else
            star(i, j, num / 3);
    }
}
int main() {
    int num;
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        for (int j = 0; j < num; j++)
            star(i, j, num);
        cout << '\n';
    }
}

분할정복을 통한 별찍기 문제이다.

num을입력받은후 각칸만다 star함수를 호출하고 이함수를통해 공백또는 별을 출력한다.

우선 예시에서 가장 기본이 되는 사각형에서 공백이 되는 공간의 좌표는 1,1 1,4 1,7

4,1 4,4 4,7 ...

즉 i%3 == 1 && j%3 == 1이라는 규칙을 찾을수있다.

다음은 9개의 사각형이 모였을때 가운데 에 비어있는 좌표는 3,3 3,4 3,5 4,3 4,4, 4,5 ...

즉 (i / 3) % 3 == 1 && (j / 3 ) % 3 == 1 라는 규칙을 찾을수 있다.

이러한 규칙을 재귀적반복으로 num/3으로 나누며 공백인지 별인지를 구별해 답을 구할수 있다.

2448 . 별찍기 11

#include<cstdio>
 
char DB[][6]=
{ "  *  ",
  " * * ",
  "*****" };
char MAP[3500][6500];
 
void solve(int n, int y, int x)
{
    if (n == 1)
    {
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 5; j++)
                MAP[y + i][x + j] = DB[i][j];
        return;
    }
    solve(n / 2, y, x + 3 * n / 2);
    solve(n / 2, y + 3 * n / 2, x);
    solve(n / 2, y + 3 * n / 2, x + 3 * n);
}
 
int main()
{
    int n;
    scanf("%d", &n);
    solve(n / 3, 0, 0);
    for(int i=0;i<n;i++,puts(""))
        for(int j=0;j<2*n-1;j++)
            printf("%c", MAP[i][j] == '*' ? '*' : ' ');
    return 0;
}

위문제와 같이 별을 찍는곳의 규칙을 알아내고 분할정복을통해 출력한다.

아직 잘이해가 가지않아 우선 구글링통해 문제를 해결하였다 스킬이 더늘어나면 공부를 해봐야겠다.