문제: www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 문제풀이 재귀 문제 출력 예시를 읽고 재귀 함수를 구현하는 문제였다. 코드 #include using namespace std; void func(int i, string underBar){ cout

문제: www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제풀이 별을 board에 모두 찍어두고 재귀를 이용하여 가운데를 지우는 방식으로 문제를 풀었다. 코드 #include using namespace std; char board[6566][6566]; void func(int x, int y, int n){ if(n==0) return; n /= 3; for(int i=x+n; in; for(int i=0; i

문제: www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 문제풀이 재귀 문제이다. 코드 #include using namespace std; int func(int x, int y, int k){ if(k==0) return 0; int half = 1= half && y < half) return 2*half*half + func(x-half,y,k-1); else return 3*half*half + func(x-half,y-half,k-1); } ..

문제: www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제풀이 대표적인 재귀 문제인 하노이탑 코드 #include using namespace std; void func(int a, int b, int k){ if(k==0) return; func(a, 6-a-b, k-1); cout

문제: www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제풀이 재귀 함수를 이용하여 문제를 풀었다. 일반적인 반복문으로 풀면 a^b는 연산 횟수에 의한 시간초과나 a^b 값의 크기로 인한 오버플로우가 일어날 수 있다. 코드 #include using namespace std; long long func(long long a, long long b, long long c){ if(b==1) return a % c; long long val = func(a,b/2,c); val = val * val % c; if(b%2==0..

문제: www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제풀이 숨바꼭질 시리즈 문제, 일차원 직선에서의 BFS로 시작점(N)에서 동생(K)까지의 최단거리를 구하는 문제이다. 다른 숨바꼭질 문제와 다르게 수빈이의 경로도 출력해주어야 하기 때문에 dist배열을 2차원으로 선언하여 점마다 현재 점의 직전 점을 저장하였다. 마지막에 동생(K)에 도착하면 K부터 N까지 경로를 역으로 추적하여 벡터에 저장 후 순서대로 출력했다. 코드..