[백준] java 알고리즘 스터디 1주차 - 재귀

11729 하노이 탑 이동 순서

📌문제 링크

https://www.acmicpc.net/problem/11729

💡 문제 풀이

1914 하노이 탑 문제와 거의 비슷하다고 생각해서 20 이상일 때 조건문만 없애주고 제출했는데 시간초과가 났다. 1914는 시간 제한이 6초였지만, 이 문제는 시간제한이 1초이기 때문에 출력 부분에서 시간초과가 난 것이었다..
StringBuilder로 한 번에 출력해 시간초과를 해결했다.

📋코드

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	static StringBuilder sb = new StringBuilder(10);
	
	public static void hanoi(int from, int between, int to, int cnt) {
		if (cnt == 1) {
			sb.append(from + " " + to).append("\n");
		} else {
			hanoi(from, to, between, cnt-1);
			hanoi(from, between, to, 1);
			hanoi(between, from, to, cnt-1);
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		BigInteger res = new BigInteger("2");
		
		System.out.println(res.pow(n).subtract(new BigInteger("1")));
		hanoi(1, 2, 3, n);
		System.out.print(sb.toString());
	}

}

⏱ 시간 복잡도

이동 횟수만큼 hanoi 함수를 호출한다. (2^n + 1)
따라서 시간 복잡도는 O(2^n)이다.

2447 별 찍기 - 10

📌문제 링크

https://www.acmicpc.net/problem/2447

💡 문제 풀이

📋코드

import java.util.Scanner;

public class Main {
	static int N;
	static char arr[][];
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
        
        // arr 배열에 별 찍기
		arr = new char[N][N];
		makeStar(0, 0, N, false);
		
        // 시간초과 방지를 위해 StringBuilder에 arr의 값 append
		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);

	}
	
	private static void makeStar(int x, int y, int size, boolean isblank) {
		
		if (isblank) {
			for (int i = x; i < x+size; i++) {
				for (int j = y; j < y+size; j++) {
					arr[i][j] = ' ';
				}
			}
			return;
		}
		
		if (size == 1) {
			arr[x][y] = '*';
			return;
		}
		
		
		int cnt = 0;
		for (int i = x; i < x+size; i+= size/3) {
			for (int j = y; j < y+size; j+= size/3) {
				cnt++;
				if (cnt == 5) {
					makeStar(i, j, size/3, true);
				}
				else makeStar(i, j, size/3, false);
			}
		}
	}

}

⏱ 시간 복잡도

N만큼 이중 for문을 수행하기 때문에 시간 복잡도는 O(N^2)이다.
N의 최댓값이 3^8(6,561)이고, 이 수를 제곱해도 43,046,721번 연산이기 때문에 제한시간 1초 안에 수행할 수 있다.
(10억 번 연산을 1초라고 가정)

1991 트리 순회

📌문제 링크

https://www.acmicpc.net/problem/1991

💡 문제 풀이

노드의 값이 알파벳이기 때문에 검색을 빠르게 할 수 있도록 인접리스트를 HashMap으로 구현했다.
현재 노드를 key로, value를 {왼쪽 자식, 오른쪽 자식}의 배열로 설정했다.

전위, 중위, 후위 순회를 재귀함수로 구현했다.
현재 노드의 값이 .일 경우 return하고, .이 아닐 경우 현재 노드의 값을 출력한다.

📋코드

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

public class Main {
	static HashMap<String, String[]> adj;
	static int N;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		String[] tmp;
		adj = new HashMap<>(N);
		
		for (int i = 0; i < N; i++) {
			tmp = br.readLine().split(" ");
			adj.put(tmp[0], new String[] {tmp[1], tmp[2]});
		}
		
		preorder("A");
		System.out.println();
		inorder("A");
		System.out.println();
		postorder("A");
	}
	
	private static void preorder(String cur) {
		if (cur.equals(".")) return;
		System.out.print(cur);
		preorder(adj.get(cur)[0]);
		preorder(adj.get(cur)[1]);
	}
	
	private static void inorder(String cur) {
		if (cur.equals(".")) return;
		inorder(adj.get(cur)[0]);
		System.out.print(cur);
		inorder(adj.get(cur)[1]);
	}
	
	private static void postorder(String cur) {
		if (cur.equals(".")) return;
		postorder(adj.get(cur)[0]);
		postorder(adj.get(cur)[1]);
		System.out.print(cur);
	}

}

⏱ 시간 복잡도

노드 개수만큼 함수를 재귀호출하기때문에 시간 복잡도는 O(N)이다.

6603 로또

📌문제 링크

https://www.acmicpc.net/problem/6603

💡 문제 풀이

kC6의 조합을 구해서 출력한다.
조합은 재귀함수로 구현했다.
S의 원소가 이미 오름차순으로 주어지고, 반복문을 인덱스 순서대로 수행하기 때문에 별도의 처리를 하지 않아도 사전 순으로 출력된다.
출력할 내용이 많기 때문에 StringBuilder를 사용했다.

📋코드

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

public class Main {
	static int K;
	static int[] arr = new int[13];
	static int[] numbers = new int[6];
	static StringBuilder sb = new StringBuilder(10);
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp;
		
		while(true) {
			tmp = br.readLine().split(" ");
			
			if (tmp[0].equals("0")) break;
			K = Integer.parseInt(tmp[0]);
			
			for (int i = 0; i < K; i++) {
				arr[i] = Integer.parseInt(tmp[i+1]);
			}
			
			combi(0, 0);
			sb.append("\n");
		}
		
		System.out.print(sb.toString());
	}
	
	private static void combi(int cnt, int start) {
		if (cnt == 6) {
			for (int num : numbers) {
				sb.append(num+" ");
			}
			sb.append("\n");
			return;
		}
		
		for (int i = start; i < K; i++) {
			numbers[cnt] = arr[i];
			combi(cnt+1, i+1);
		}
	}

}

⏱ 시간 복잡도

조합을 구하는 데 O(2^N)이 걸린다.
입력 최댓값이 13이기 때문에 시간제한 1초를 통과할 수 있다.

1992 쿼드트리

📌문제 링크

https://www.acmicpc.net/problem/1992

💡 문제 풀이

재귀함수로 구현했다.

• 인자 : sr(start row; 시작 행 좌표), sc(start column; 시작 열 좌표), len(탐색할 배열의 길이)
• 기저 조건 :
  1. len이 1일 때 : 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 숫자를 출력한다.
  2. 현재 배열에 0만 있거나 1만 있을 때 : 0이나 1을 출력한다.
• 유도 부분 (0과 1이 모두 있을 때)
  왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서대로 시작 좌표와 len/2를 인자로 하여 재귀 호출한다. 4가지 세트를 괄호로 감싸준다.

📋코드

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

public class Main {
	static int N;
	static int[][] arr;
	static StringBuilder sb = new StringBuilder(10);

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] tmp;

		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];

		for (int i = 0; i < N; i++) {
			tmp = br.readLine().split("");
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(tmp[j]);
			}
		}
		
		comp(0, 0, N);

		System.out.print(sb.toString());

	}

	private static void comp(int sr, int sc, int len) {
		if (len == 1) {
			for (int i = sr; i < sr + len; i++) {
				for (int j = sc; j < sc + len; j++) {
					sb.append(arr[i][j]);
				}
			}
			return;
		}

		int one = 0, zero = 0;

		for (int i = sr; i < sr + len; i++) {
			for (int j = sc; j < sc + len; j++) {
				if (arr[i][j] == 1)
					one++;
				else
					zero++;
				
				if (one > 0 && zero > 0) break;
			}
		}
		
		if (one > 0 && zero > 0) {
			int newlen = len/2;
			sb.append("(");
			comp(sr, sc, newlen);
			comp(sr, sc + newlen, newlen);
			comp(sr + newlen, sc, newlen);
			comp(sr + newlen, sc + newlen, newlen);
			sb.append(")");
		} else {
			if (zero > 0 && one == 0) {
				sb.append("0");
			} else if (one > 0 && zero == 0) {
				sb.append("1");
			}
		}
	}

}

⏱ 시간 복잡도

입력: N*N
재귀 호출 : N*N
-> O(N^2)
N의 최댓값이 64이기 때문에 제한시간 2초 안에 통과할 수 있다!