Algorithm/Baekjoon
[백준] 2447 별찍기 10 - Java
[백준] 2447 별찍기 10 - Java
2022.05.17문제를 잘 이해해보자. N * N 크기의 배열을 생성한다. (N은 3의 제곱수) 배열을 9등분하며 계산을 진행한다. 이 때 9등분한 배열의 가운데 부분은 빈 칸으로 남기고, 나머지 8칸의 배열에 대해서 계속해서 계산을 진행한다. N이 3의 제곱수이므로 오류 없이 이어나갈 수 있다. 종료 조건은 N이 1이 되는 경우이고, 이 때는 별을 찍어주자. 어떻게 재귀를 사용해 풀이할 지 생각해내는게 중요한 문제였다. import java.util.*; import java.io.*; public class Main { static int N; static char[][] map; static StringBuilder sb = new StringBuilder(); public static void main(Strin..
[백준] 1992 쿼드트리 - Java
[백준] 1992 쿼드트리 - Java
2022.05.17전에 풀었던 종이문제와 색종이문제와 같은 방식으로 풀 수 있다. 다만, 분할정복을 수행하기 전 괄호를 프린트해주고, 분할정복을 수행한 후 괄호를 프린트해주자. import java.util.*; import java.io.*; public class Main { static int N; static int[][] map; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine());..
[백준] 2630 색종이 만들기 - Java
[백준] 2630 색종이 만들기 - Java
2022.05.16지난번에 풀었던 종이의 개수 문제와 똑같은 문제이다. 믿음을 가지고 재귀를 구현하자. import java.util.*; import java.io.*; public class Main { static int[][] map; static int N; static int[] ans = new int[2]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); map = new int[N][N]; StringTokenizer st; for(int i=0; i
[백준] 1780 종이의 개수 - Java
[백준] 1780 종이의 개수 - Java
2022.05.16함수를 어떻게 설정할 지 생각해보자. 일단 이차원 배열을 사용해야 될 것 같다. 이차원 배열을 넘겨줄 필요는 없고, 전역변수로 설정한 후 인덱스를 적절히 조작하며 풀어야겠다. 입력은 3의 제곱수임이 보장된다. 그러면 종료 조건은? 종료 조건은 따로 명시하지 않아도 괜찮을 것 같다. 마지막 단위는 3이 아니라 1이 될텐데, 1 단위로 탐색을 시작하면 같은 수로 이루어진 배열인지 검사할 때 걸리니까.. 일단 작성하고 스스로를 믿자. import java.util.*; import java.io.*; public class Main { static int N; static int[][] map; static int[] ans = new int[3]; public static void main(String[] ..
[백준] 1074 Z - Java
[백준] 1074 Z - Java
2022.05.161. base condition 작성 2. 분기에 따른 코드 작성 3. 믿음 절차적 사고에서 벗어나자. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int R = Integer.parseInt(st.nextToken()); int C = ..
[백준] 2251 물통 - Java
[백준] 2251 물통 - Java
2022.05.14C가 꽉 찬 상태로 시작해서, 물통의 물을 옮기면서 전이할 수 있는 모든 상태를 간선으로 표현해 그래프를 완성한 후 dfs혹은 bfs를 돌려서 풀 수 있다. 1. "어떻게 그래프로 표현할 수 있을까?"를 생각해보자. (연습 많이 필요) 2. 클래스(구조체)를 만들어 그래프 탐색에 활용하자. import java.util.*; import java.io.*; public class Main { static int[] limit = new int[3]; static boolean[] possible; static boolean[][][] visit; public static void main(String[] args) throws IOException { BufferedReader br = new Buffe..
[백준] 2535 아시아 정보올림피아드 - Java
[백준] 2535 아시아 정보올림피아드 - Java
2022.05.13하라는대로 하면 되는 문제.. 클래스를 사용해 Comparator를 정의하고 정렬을 수행했다. import java.util.*; import java.io.*; 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()); candidate arr[] = new candidate[N]; for(int i=0; i
[백준] 2667 단지번호붙이기 - Java
[백준] 2667 단지번호붙이기 - Java
2022.05.13인접한 집들의 모임은 단지가 된다. 단지의 수와 단지 안에 있는 집의 수를 구하는 문제이니.. 지도를 그래프로 표현하고 집들을 묶어주면 될 것 같다. 몇 가지 팁을 알고 가자. 1. 격자점에서 탐색을 수행할 때, 점의 이동을 표현할 때 배열을 통해 구현하면 편하다. (2차원배열 / 1차원배열2개 모두 가능) 2. 지도를 입력받을 때 공백 없이 입력된다면 String의 1차원배열을 사용해보자. dfs와 bfs 두 가지 방법을 사용할 수 있다. import java.util.*; import java.io.*; public class Main { static int N; static int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}}; // 격자를 탐색할 때 사용할 수 있는 테크..
[백준] 1260 DFS와 BFS - Java
[백준] 1260 DFS와 BFS - Java
2022.05.12배열을 활용해서 체크하는게 좀 더 편한 것 같다. dfs와 bfs를 구현할 때 파이썬 느낌으로 forEach문을 사용하면 좀 더 직관적으로 작성할 수 있다. import java.util.*; import java.io.*; public class Main { static int N; static int M; static int V; static ArrayList[] adj; static boolean[] visit; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamR..
[백준] 1394 암호 - Java
[백준] 1394 암호 - Java
2022.05.09암호에 쓰이는 문자들의 후보의 길이와 암호의 길이를 잘 살펴보자. 후보의 길이에 따라 시도하는 횟수가 점점 증가한다. abcd가 후보라고 생각해보자. 길이가 1인 암호 : a b c d (4) 길이가 2인 암호 : aa ab ac ad / ba bb bc bd / ca cb cc cd / da db dc dd (4 * 4) ... 이런 식으로 후보문자열의 길이만큼 계속 곱해지는 형태를 보인다. 그렇다면, 주어진 암호의 길이를 통해 답을 어느정도 유추할 수 있을 것 같다. 그런데, 암호의 처음부터 계산해서 세기 시작하면 해당 자릿수 전까지의 시도 횟수는 쉽게 구할 수 있지만, 그 다음 처리가 힘들어진다. 암호의 뒤에서부터 역순으로 시도 횟수를 구해보자. 이를 위해 문자열 후보가 입력되는 순서를 알아야한다...
[백준] 1644 소수의 연속합 - Java
[백준] 1644 소수의 연속합 - Java
2022.05.09에라토스테네스의 체 방식으로 입력받은 N 이하의 소수 배열을 만든 후 항상 하던대로 투포인터 방법을 활용해 풀 수 있는 문제이다. R을 조작할때는 조건식에 합이 N이 넘어가는 조건을 포함시켜 작성하는게 좀 더 깔끔해 보인다. import java.util.*; import java.io.*; 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()); boolean[] prime_chk = new boolean[N + 1..
[백준] 15565 귀여운 라이언 - Java
[백준] 15565 귀여운 라이언 - Java
2022.05.08투 포인터를 사용해서 풀 수 있는 문제이다. 정형화 된 방법을 익히고 언제 어디서든 사용할 수 있도록 하자. 1. 배열 인덱스의 시작은 1부터 시작하도록 설정하자. 2. L과 R을 조작할 때 L은 1부터, R은 0부터 시작하고 while로 R을 조작할 때 R을 1증가시키면서 시작하자. 3. 항상 문제를 잘 읽자. 배열 인덱스의 시작을 1부터 시작하도록 설정하는거는 단순히 편의를 위해서이다. 이분 탐색을 진행할 때는 mid값을 제대로 구하기 위해 1부터 설정했었는데.. 이게 손에 익어서 계속 쓰게 됐다. 위의 형식은 문제 조건에 따라서 얼마든지 바뀔 수 있지만, 그래도 풀이의 틀을 잡아놓으면 접근하기 편한 것 같다. import java.util.*; import java.io.*; public class..