알고리즘 설명
재귀 : 하나의 함수에서 자기 자신을 다시 호출해 작업을수행하는 알고리즘
절차지향적사고를 버리고 수학적 귀납법으로 문제를 해결해야함
-재귀 함수의 조건
특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야함(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 . 하노이 탑
- 함수의 정의
void func(int a, int b, int n)
원판 n개를 a번 기둥에서 b번 기둥으로 옮기는 방법을 출력하는 함수
- base condition
n= 1일 때 cout << a <<' '<< b << '\n';
- 재귀식
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
를보고 문제를 다시 이해해보니 조금더 이해가된거같다.
- 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;
}
위문제와 같이 별을 찍는곳의 규칙을 알아내고 분할정복을통해 출력한다.
아직 잘이해가 가지않아 우선 구글링통해 문제를 해결하였다 스킬이 더늘어나면 공부를 해봐야겠다.
