백준 - 단계별로 풀어보기 - JAVA (11단계 : 재귀 / 6문제) (2022.12.31 토)

1단계 : 10872번 / 팩토리얼

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

public class Main{

    public static void main(String args[]) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       

        int N = Integer.parseInt(br.readLine());
        int pack = 1;
        for (int i=1; i<=N; i++){
            pack = pack * i;
        }
        System.out.println(pack);
    }
}

---

2단계 : 10870번 / 피보나치 수 5

* 동적 계획법 (DP)를 사용한 방법

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

public class Main{

    public static int[] memo = new int[21]; // 0~20

    public static void main(String args[]) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int N = Integer.parseInt(br.readLine());
        System.out.println(fidonacci(N));
    } // main

    public static int fidonacci(int n){
        if (n == 0){
            return 0;
        } else {
            if (memo[n] != 0){
                return memo[n];
            }
            else {
                if (n == 1 || n == 2){
                    memo[n] = 1;
                } else {
                    memo[n] = fidonacci(n-1) + fidonacci(n-2);
                }
                return memo[n];
            }
        }
    } // fidonacci
} // Main

 

* 재귀 호출 방식으로 구현

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

public class Main{

    public static void main(String args[]) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int N = Integer.parseInt(br.readLine());
        System.out.println(fidonacci(N));
    } // main

    public static int fidonacci(int n){
        if (n == 0){
            return 0;
        } else {
            if (n == 1 || n == 2){
                return 1;
            }
            else {
                return fidonacci(n-1) + fidonacci(n-2);
            }
        }
    } // fidonacci
} // Main

---

3단계 : 25501번 / 재귀의 귀재 (팰린드롬)

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

public class Main{
    public static int count = 0;

    public static int recursion(String s, int l, int r){
        count++;
        if(l >= r) return 1;
        else if(s.charAt(l) != s.charAt(r)) return 0;
        else return recursion(s, l+1, r-1);
    }
    // 팰린드롬이면 1, 아니면 0
    public static int isPalindrome(String s){
        return recursion(s, 0, s.length()-1);
    }

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++){
            String str = new String(br.readLine());
            System.out.println(isPalindrome(str)+" "+count);
            count = 0;
        }
    }

} // Main

---

4단계 : 24060번 / 알고리즘 수업 - 병합 정렬 1

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main{

    static int[] tmp;
    static int count = 0;
    static int K; // 저장 횟수
    static int result = -1; // N = 0일 경우, 초기화

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        K = Integer.parseInt(st.nextToken());

        tmp = new int[N];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        } // 배열 입력 완료!

        marge_sort(arr, 0, arr.length - 1);
        bw.write(result+"\n");
        bw.flush();
        bw.close();

    }

    static void marge_sort(int[] a, int left, int right){
        if (left < right){
            int mid = (left + right) / 2;
            
            marge_sort(a, left, mid);
            marge_sort(a, mid + 1, right);
            
            marge(a, left, mid, right);
        }
    }

    static void marge(int[] a, int left, int mid, int right){
        int l = left;
        int r = mid + 1;
        int t = 0;

        while(l <= mid && r <= right){
            if (a[l] <= a[r]){
                tmp[t++] = a[l++];
            }
            else {
                tmp[t++] = a[r++];
            }
        }

        while(l <= mid){
            tmp[t++] = a[l++];
        }
        while(r <= right){
            tmp[t++] = a[r++];
        }

        t = 0;
        l = left;

        while(l <= right){
            count ++;
            if (count == K){
                result = tmp[t];
                break;
            }
            a[l++] = tmp[t++];
        }
    }  
} // Main

---

5단계 : 2447번 / 별 찍기 - 10

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main{

    static char[][] arr;
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); 

        arr = new char[N][N];
        star(0, 0, N, false);

        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                bw.write(arr[i][j]);
            }
            bw.write("\n");
        }
        bw.flush();

        
    }

    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;
        }
        
        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) { // 5번째 블럭일 경우, 공백칸
                    star(i, j, size, true);
                }
                else{
                    star(i, j, size, false);
                }
            }
        }
    }

} // Main

https://st-lab.tistory.com/95

[백준] 2447번 : 별 찍기 - 10 - JAVA [자바]

---

6단계 : 11729번 / 하노이 탑 이동 순서

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

public class Main{

    static int count = 0;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine()); // 원판 개수
        
        hanoi_tower(N, '1', '3', '2');
        bw.write(count+"\n");
        bw.write(sb.toString());

        bw.flush();
        bw.close();
    }

    /*
     * @param n 원판 개수
     * @param from 출발 막대
     * @param to 도착 막대
     * @param other 여분막대
    */
    static void hanoi_tower (int n, char from, char to, char other){
        count ++;
        if(n == 1){
            sb.append(from).append(" ").append(to).append("\n");
        }
        else {
            hanoi_tower(n-1, from, other, to);
            sb.append(from).append(" ").append(to).append("\n");
            hanoi_tower(n-1, other, to, from);
        }
    }
} // Main

---