재귀 원리
들어가기 앞서 재귀 함수가 어떻게 구성되고 진행되는지 알아보려한다! 초보몽키님의 개발공부로그 블로그, Stranger's lab님의 블로그 글을 참고하여 작성하였다.
사진 출처: Stranger's lab
- 재귀: 자기 자신을 재참조하는 방법/ 함수 정의 내 같은 이름의 함수가 올 때 이를 재귀 함수라 부름
-> 탈출 조건이 있어야 stack overflow 방지
-> 재귀 함수 끝나는 지점을 정확히 구현해야함
->> 함수의 첫 항 부분에 초점을 맞추며, 다음 항이 어떻게 올지 규칙성을 찾아보자
10872번 팩토리얼
import java.util.Scanner;
class Main {
public static int fac(int x){
if(x<=1)
return 1;
return x*fac(x-1);
}
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int N=sc.nextInt();
int ans=fac(N);
System.out.println(ans);
}
}- 재귀함수를 만들면 더 간단하다. 갖고 있는 수에서 하나씩 줄어나가는 그런 모습을 생각해보면... 제일 덜어져 나가 줄어질때까지는 해당 함수에 변수보다 크기가 작은 수와 x를 곱하고 다 나가떨어진 경우 1을 return한다.
10870번 피보나치 수 5
import java.util.Scanner;
public class Main {
static int fiv(int x){
if(x==0){
return x;
}
else if(x==1){
return 1;
}
return fiv(x-2)+fiv(x-1);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.print(fiv(n));
}
}-
처음에 런타임에러가 떠서 배열의 수 어느 부분이 틀렸는지 헤맸다. 배열말고 재귀로 해보자! 해서 다시 곰곰히 생각한 결과,, 재귀는 어떤 걸 최종적으로 나타낼 건지 결론을 생각해보면 if문에 따라 조건을 맞춰 표현할 수 있다. fiv함수에 x부터... 0까지 내려가는 걸 생각해보면 if문에 0일때, 1일때 조건을 걸고, 기본 return값으로 fiv(x-2)+fiv(x-1)을 설정하여 n을 대입시 n은 n-1, n-2, n-3, ..., 0이 되어 최종값을 도출해낼 수 있다.
-
배열에서 java.lang.ArrayIndexOutOfBoundsException 에러가 났는데, 이 이유는 for문 안에서 0번, 1번 항을 초기화 안해줘서였다!
2447번 별 찍기
import java.util.Scanner;
public class Main {
static char[][] arr;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
arr = new char[N][N];
star(0, 0, N, false);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
sb.append(arr[i][j]);
}
sb.append('\n');
}
System.out.print(sb);
}
static void star(int x, int y, int N, boolean blank) {
// 공백칸일 경우
if (blank) {
for (int i = x; i < x + N; i++) {
for (int j = y; j < y + N; j++) {
arr[i][j] = ' ';
}
}
return;
}
// 더이상 쪼갤 수 없는 블록일 때
if (N == 1) {
arr[x][y] = '*';
return;
}
/*
N=27 일 경우 한 블록의 사이즈는 9이고,
N=9 일 경우 한 블록의 사이즈는 3이듯
해당 블록의 한 칸을 담을 변수를 의미 size
count는 별 출력 누적을 의미
*/
int size = N / 3;
int count = 0;
for (int i = x; i < x + N; i += size) {
for (int j = y; j < y + N; j += size) {
count++;
if (count == 5) { // 공백 칸일 경우
star(i, j, size, true);
} else {
star(i, j, size, false);
}
}
}
}
}- 이 문제는 계속 고민해봐도 못풀겠어서 Stanger's lab님의 코드에 도움받았다. 분명 별 9칸에 가운데 하나 빠진 그 모양이 중심인데...하며 어떻게 하면 칸 수가 3배씩 줄어들어도 그 모양이 유지되나 고민했다.
- 우선 첫 항은 별 9칸에 가운데 하나 빠진 모양이고, 다음 항은 첫 항의 9칸 크기가 하나의 항이 되어 또 다시 9칸을 구성하고, 가운데는 비워놓는다.
- 그리고 생각해야할 부분은 별 표시가 nXn식으로 되어있으므로, 2차원 배열로 표현하는 것이 편하다. 배열을 arr라 하고, 항상 공백을 나타내는 부분은 arr[1][1]이다. n=27일 때 9개의 블록으로 구분하고, arr[1][1]과 같이 공백을 만족하는 부분은 공백으로 채운다. 아닌 부분은 재귀호출!
- n=9로 넘어가보면 또 다시 9개의 블록으로 나누어 공백인 부분과 아닌 부분으로 나누고, 공백 아닌 부분은 재귀호출한다. n 점점 줄어들면 n=1일 때가 되는데, 해당 구역의 배열을 공백 또는 별로 채운다!
11729번 하노이 탑 이동 순서
import java.util.Scanner;
public class Main {
public static int count;
public static StringBuilder sb = new StringBuilder();
public static void tower(int x, char from, char tmp, char to){
++count;
if(x==1){
sb.append(from+" "+to+"\n");
}
else{
tower(x-1, from, to, tmp);
sb.append(from+" "+to+"\n");
tower(x-1, tmp, from, to);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
tower(n, '1', '2', '3');
sb.insert(0, count+"\n");
System.out.println(sb);
}
}- 작년에 C언어 수업 때 배웠던 하노이탑 이동 문제! 버벅였던 부분은 처음에 얼마나 움직였는지 수를 먼저 print하는 부분..! StringBuilder를 사용하고 0번째 자리에 insert하니 가능했다.
- Scanner 쓰면 성능이 떨어지니 StringBuilder 사용하는 게 좋다!
StringBuilder 사용법
자바에서 String은 불변객체로 더하는 행위는 메모리 할당, 해제를 발생시켜 성능적으로 좋지 않다. StringBuilder는 String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아닌, 기존의 데이터에 더하는 방식을 사용하기에 속도도 빠르며 상대적으로 부하가 적다.
- 만들어진 문자열을 출력하기 위해 StringBuilder 인스턴스인 sb의 toString()을 사용한다.
- 문자열을 더할 땐 append() 사용
- insert()에 넣고 싶은 문자열 항을 적어 그 자리에 넣을 수 있다.
StringBuilder sb = new StringBuilder(); sb.append("ABC"); sb.append("DEF"); System.out.println(sb.toString());
뭐든지 할 수 있따 🐶