본문 바로가기
반응형

백준/분할정복9

백준 1992. 쿼드트리 🅰 백준 1992. 쿼드트리 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net ✏️ 문제 풀이 영상이 4개로 압축되어 진행되므로 4개의 시작점을 구해서 재귀를 돌려주었다. 또한 출력을 맞춰주기 위해 재귀가 시작되기 전에 "("를 출력해주고, 재귀가 끝나면 ")"를 출력해주었다. ✏️ 소스코드 import java.util.*; import java.io.*; public class Main { static int N; static int tree[][]; public static void main(.. 2021. 9. 6.
백준 11729. 하노이탑 🅰 백준 11729. 하노이탑 ✏️ 문제 풀이 ✏️ 소스코드 package divideandconquer; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; /*sysout을 사용하면 안되고 bufferedwriter를 사용해서 한번에 출력해줘야한다. * 하노이탑의 최소 이동 순서 = 2^N-1*/ public class Main_실버2_11729_하노이탑 { private static int cnt; private static Strin.. 2021. 9. 6.
백준 1780. 종이의 개수 🅰 백준 1780. 종이의 개수 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net ✏️ 문제 풀이 재귀를 이용하여 문제를 풀어주었다. 쿼드트리, 종이자르기 등과 같이 비슷한 문제로 접근하였다. 종이를 9개로 나누기 때문에 9개의 시작점을 찾아서 재귀를 돌려주었고, 첫 시작 값을 비교하여 전부 다 같은 숫자이면 각 숫자에 맞는 변수를 ++해줘서 종이의 개수를 count 해주었다. ✏️ 소스코드 package divideandconquer; import java.util.*; import java.io... 2021. 9. 6.
백준 2447. 별찍기 10 🅰 백준 2447. 별찍기 10 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net ✏️ 문제 풀이 N크기만큼 2차원 배열을 생성하여 재귀 규칙에 따라 데이터를 넣은 후 출력을 해주었다. 규칙을 보면 다섯번째 순서일 때 공백칸을 출력하므로 count와 boolean형 check변수를 이용하여 가운데 빈 부분을 체크해주었다. 재귀 수행 후 기저조건으로는 check = true일 때(" "), N==1일때(*)를 지정해주었다. ✏️ 소스코드 package divideandconquer; i.. 2021. 9. 6.
백준 2448. 별찍기 11 🅰 백준 2448. 별찍기 11 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net ✏️ 문제 풀이 재귀를 이용하여 삼각형을 3등분을 한 다음 같은 모양의 삼각형을 찍어주었다. 일단 삼각형을 프린트 할 수 있는 함수를 하나 생성하고, 재귀함수를 생성해주었다. 재귀함수 내에서는 N==3(삼각형 높이가 3)이 될때까지 재귀를 돌린 후 프린트함수를 통해 배열에 저장을 해주었다. 시작 꼭지점을 기준으로 삼각형을 3등분 해주었다. star(N / 2, x, y); //중심 star(N / 2, x + N / 2, y + N / 2); //좌 star(N / 2, x + N .. 2021. 9. 6.
백준 11728. 배열합치기 🅰 백준 11728. 배열합치기 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net ✏️ 문제 풀이 mergesort의 전형적인 문제이다. 배열을 나눠서 다시 합치는 과정을 통해 정렬을 하는데 합치는 부분만 따로 구현을 해주었다. 이미 입력 데이터는 정렬되어 있기 때문에 arrN 배열과 arrM배열을 0번째 부터 탐색을 해줘서 더 작은 수를 sb에 추가해주었다. 만약 index를 배열 끝까지 다 방문하였다면 if문을 이용하여 그 배열을 제외한 다른 배열의 데이터를 계속해서 넣어주.. 2021. 9. 6.
백준 10816. 숫자카드2 🅰 백준 10816. 숫자카드2 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ✏️ 문제 풀이 HashMap을 이용하여 중복되는 카드의 개수를 저장해주었다. 그 외에는 숫자카드1과 마찬가지로 이분탐색을 하면서 재귀를 구현하여서 문제를 풀었다. ✏️ 소스코드 package divideandconquer; import java.util.*; import java.io.*; /*HaseMap을 이용하여 key,value값을 저장해주었다.*/ public class Main_실버4_.. 2021. 9. 6.
백준 1074. Z 🅰 백준 1074. Z 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net ✏️ 문제 풀이 백준의 색종이, 쿼드트리랑 비슷한 문제이다. 시간제한이 0.5초이기 때문에 모든 케이스를 탐색할 수는 없다. 재귀를 이용하여 2차원배열을 4등분하고, r,c가 위치하고 있는 배열만 탐색하도록 구현하였다. 그리고 나눠진 배열의 시작점을 매개변수로 보내주어서 r,c를 몇번째로 방문했는지 체크해주었다. ✏️ 소스코드 package divideandconquer; import java.util.Scanner; public.. 2021. 9. 5.
백준 10815. 숫자 카드 🅰 백준 10815. 숫자 카드 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net ✏️ 문제 풀이 숫자를 정렬한 다음 이분탐색을 이용하여 문제를 풀었다. 중간값을 비교하여 탐색하는 과정을 재귀로 구현하였는데 생각보다 수행시간이 오래걸렸다. 그래서 재귀방식 말고 main문 안에서 바로 답을 찾도록 구현 하였는데 0.1초밖에 안 줄어들었다. start, end, middle 값 설정 목표값 middle과 비교하여 1. ansmiddle이면 start = middle+1 middle = .. 2021. 8. 30.

티스토리툴바