분할정복
-
[Java] 백준 2447 별찍기 10Programming/Algorithm 2021. 3. 9. 00:48
문제 크기 3의 패턴이 주어지고, 크기가 3이상일 때 가운데는 공백 나머지는 n/3 패턴으로 둘러싼 형태의 모양을 출력하는 문제이다. 풀이 공백이 되어야 하는 부분과 아닌 부분으로 분할해서 재귀하는 것이 풀이의 핵심이다. - n을 3으로 나누어 현재 영역을 9등분한다. - 이 때 가운데는 공백이라는 조건이 있으므로, 5번째 영역은 항상 공백이 되어야 한다. - n이 1이라면 별을 출력하고, 아니라면 나누어진 영역을 재탐색한다. 코드 import java.io.*; public class Main { static char[][] map; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRea..
-
[Java] 백준 1992 쿼드트리Programming/Algorithm 2021. 3. 9. 00:36
문제 주어진 영역 내의 숫자가 모두 같은 숫자면 해당 숫자를 출력하고, 아니라면 영역을 4등분하여 숫자가 같은지 다시 검사를 하는 문제이다. 풀이 1. 현재 영역의 숫자를 검사 2. 모두 일치하지 않는다면 현재 변의 길이(n)을 1/2하고, 현재 좌표를 기준으로 4영역으로 분할하여 함수를 재호출 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int[][] map; static StringBuilder sb; public static void main(String[] args) throws IOException { BufferedRea..
-
[Java] 백준 11729 하노이 탑 이동 순서Programming/Algorithm 2021. 3. 5. 19:59
문제 하노이의 탑에 있는 N개의 원판을 '1'에서 '3'으로 이동시킬 때, 탑의 이동 순서를 출력하는 문제이다. 하노이의 탑 풀이는 공식처럼 외워서 사용하는 편이 편한 것 같다. 핵심적인 논리는 N개의 원판을 '1'에서 '3'으로 이동시키기 위해 우선 N-1개를 '1'에서 '2'(도움닫이 공간)으로 이동시킨 후, 마지막 1개의 원판을 '3'으로 이동시키는 것이다. 이동시킨 후엔 '2'(도움닫이 공간)으로 이동시킨 원판을 다시 '3'으로 이동하는 방식으로 진행한다. 그림을 그려가며 이해하는 것이 좋다. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main {..
-
[Java] 백준 1780 종이의 개수Programming/Algorithm 2021. 3. 5. 19:53
문제 잘라진 종이가 한 숫자로만 이루어져 있는지를 검사하고 그렇다면 종이 개수를 추가하고, 아니라면 9등분으로 나눠 다시 종이 내의 숫자를 검사하는 문제이다. 9등분으로 나누는 부분을 재귀로 처리하였다. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; static int[][] map; static int[] res; public static void main(String[] args) throws IOException { solution(); } static v..
-
[Java] 백준 11728 배열 합치기Programming/Algorithm 2021. 3. 5. 19:48
문제 정렬되어 있는 배열 A와 B가 주어질 때, A와 B를 합친 새로운 배열을 정렬된 형태로 출력하는 문제이다. A와 B의 가장 작은 값을 비교하여 더 작은 값을 새로운 배열에 추가하고 인덱스를 하나 증가시키는 방식을 사용한다. 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader..