[백준-Java] 재귀 1~3번

오늘 포스팅할 내용은 '재귀'에 대한 알고리즘이다.

수업에서 들었을 때는 너무 어려워서 대충 훑고 지나갔는데
이번에 본격적으로 이해하려니 그때의 내가 너무 원망스러웠다.

10872번) 팩토리얼

재귀의 핵심은 끝맺음이라 할 수 있다.
반복이 멈추는 지점을 염두해두고 꼭 코딩해야 한다.

팩토리얼은 입력받은 n값이 1이 될 때까지 f(n-1)을 계속해서 호출한다. 여기서 나는 결과값을 매개변수에 넣어 마지막에 그 결과값을 리턴해주도록 코드를 짰다.

문제를 풀고 나중에야 이것이 꼬리재귀인 것을 알았다.
수업때 이해 못했던 내용이었는데 내가 직접 쓰고있어서 신기했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int result = 1;
        System.out.println(pact(T, result));
    }

    public static int pact(int a, int res){
        res = res * a;
        if(a <= 1) return res; // 종단부
        return pact(a-1, res); // 꼬리재귀를 위해 함수 그대로 리턴
    }
}

10870번) 피보나치 수열

혹시 피보나치 수열을 모르는 사람을 위해 설명을 해보자면, 피보나치 수열은 위와같이 첫항과 둘째항이 1이며 다음 항부터는 이전 항들의 합인 수열을 말한다.

예를 들어, 넷째달이 f(4)이면 f(4)=f(3)+f(2)겠고, f(4)=f(2)+f(1)+f(2)이기 때문에 f(4)는 3이 된다.

식으로 표현한다면 fibo(n-1)+fibo(n-2)이다.
항과 둘째항이 정해져 있으므로 함수의 매개변수에 들어가는 값이 1 또는 2가 되면 재귀를 멈추게 하는 것이 피보나치 수열 알고리즘의 핵심이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        System.out.println(fibo(T));
    }
    public static int fibo(int t){
        if(t == 0) return 0;
        if(t == 1) return 1;
        if(t == 2) return 1;
        return fibo(t-1) + fibo(t-2);
    }
}

2447번) 별찍기 - 10

문제를 처음 봤을때 이런 기괴한 별찍기는 처음봤다.

이 문제의 핵심은 네모 안의 빈공간이 어떻게 생기는지이다.

작은 사각형 하나를 생각해보자. 3*3일때 빈공간의 좌표는 (1,1)이다.
그 옆의 네모는 3칸 이동한 (1,4)일 것이다.

위, 아래 모두 같을 것이기 때문에 x와 y좌표 모두 3으로 나눈 나머지가 1이여야 한다.

이를 99에 대입해보자. 99는 (3,3)~(3,5)이다. 그 옆 네모는 6칸 이동한 (3,12)~(3,15)일 것이다.

위의 식과 같아지기 위해서는 모든 좌표에 3을 나눠주면 해결이 된다.
이러한 방식으로 27*27일때는 9를 나눠주면 해결이 될 것이다.

여기까지 해결을 했는데도 시간초과가 떠서 너무 막막했다.
원인을 찾아보다가 반복할 때마다 print함수를 호출한다는 것이 눈에 들어왔고, 출력방식을 StringBuilder로 바꾸어보았다.

StringBuilder는 출력하고 싶은 문자열을 append로 추가시켜서 한번에 문자열을 출력하는 클래스이다.

예전 문제에서 입력에서 효율을 높이기 위해 BufferReader를 쓴다는 것을 알고있었는데 출력 또한 있다는 것을 이번에야 알았다.

앞으로 자주 쓰는 습관을 들여야겠다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for(int i = 0; i < T; i++){
            for(int j = 0; j < T; j++)
                func(i,j, T, sb);
            sb.append("\n");
        }
        System.out.print(sb);
    }
    public static void func(int i,int j, int t, StringBuilder sb){
        if((i/t) % 3 == 1&& (j/t)%3 == 1)sb.append(" ");
        else{
            if(t/3 == 0) sb.append("*");
            else func(i, j, t/3, sb);
        }
    }
}