Algorithm
[백준] 5426 비밀 편지 - Java
[백준] 5426 비밀 편지 - Java
2022.05.19입력받은대로 2차원 배열에 저장하고 뒤에서부터 시작해 읽어 주면 쉽게 풀 수 있는 문제이다. 조금 다르게 풀어보자. 배열을 회전시켜서 풀 수 있지 않을까? 2차원 배열을 시계 방향으로 90도 회전하는 메서드를 구현한 후 입력받은 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)); int N = Integer.parseInt(..
[백준] 6588 골드바흐의 추측 - Java
[백준] 6588 골드바흐의 추측 - Java
2022.05.171. 리스트로 접근하면 시간 초과가 발생한다. 2. 이중 반복문으로 모든 소수쌍을 찾는 식으로 접근하면 시간 초과가 발생한다. 3. 처음에 찾은 소수가 b - a 값이 최대인 소수이다. 한개의 소수를 찾으면 다른 수는 정해진다. 이 부분에 집중해 시간 초과 없이 풀어보자. 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)); StringBuilder sb = new StringBuilder(); boolean prime..
[백준] 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 = ..
재귀
재귀
2022.05.16절차지향적인 사고를 버려야 재귀 파트를 이해할 수 있다. 재귀함수는 base condition(종료조건)이 있어야 하고, 모든 입력은 base condition으로 수렴해야 한다. 재귀함수를 사용하면 반복문을 사용하는 것 보다 효율적이지 않은 경우가 많고, 적절히 dp를 사용하지 않으면 계산했던 결과를 또 계산하는 경우가 많이 생길 수 있어 조심스럽게 사용해야 한다. 그럼에도 재귀를 이용하면 굉장히 편하게 작성할 수 있는 경우나, 재귀를 사용해야만 작성할 수 있는 코드들이 있으니 재귀를 포기할 수는 없다. a에서 a/2를 호출하고 a가 1에서 return을 만나는 함수가 있다고 해 보자. a가 1000이면 1000 -> 500 -> 250 -> 125 -> 62 -> 31 -> 15 ..... 이런 방식..
[백준] 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..