Algorithm/Baekjoon
[백준] 1600 말이 되고픈 원숭이 - Java
[백준] 1600 말이 되고픈 원숭이 - Java
2022.08.13K번만 나이트처럼 움직일 수 있다. 격자 위를 이동하면서 나이트처럼 움직인 수를 함께 확인해야 한다. 3차원 배열을 사용하자. bfs를 사용하면 제일 처음으로 목적지에 도착하면 그 때의 이동 횟수가 최소임을 보장할 수 있다. 바로 리턴해준다. 3차원 배열을 사용해 모든 경우를 확인할 수 있다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int[][] map; static int K, N, M; static int ans = -1; static int[] dr = {-1,1,0,0}; static int[] dc = {0,0,-1,1}; static int[] hr = {-2,-2,-1,-1,1,1..
[백준] 16235 나무 재테크 - Java
[백준] 16235 나무 재테크 - Java
2022.08.13하라는대로 하면 된다.. 이런 문제는 작업마다 메서드를 만들어서 접근해야 실수를 줄일 수 있다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int N; static int[][] map; static int[][] A; static ArrayList[][] tree; static int[][] death; static int dr[] = {0,0,-1,1,-1,1,-1,1}; static int dc[] = {-1,1,0,0,-1,1,1,-1}; public static void main(String[] args) throws Exception { BufferedReader br = new Buf..
[백준] 25417 고속의 숫자 탐색 - Java
[백준] 25417 고속의 숫자 탐색 - Java
2022.08.07걸어가는 경우와 뛰어가는 경우 두 가지를 모두 고려해야 한다. visit을 boolean타입이 아니라 int로 설정한 후, 초기값을 -1로 초기화하고 최단거리로 가는 경우면 계속해서 갱신해주는 방식으로 풀었다. visit을 boolean으로 설정하는 대신, Locate객체에 cnt변수를 추가하고 먼저 뛰어가게 한 후 걸어가는 경우를 확인하는 방식으로 bfs를 돌려도 해결할 수 있을 것 같다. 중간에 cur.r 대신 r으로 바꿔써서 시간낭비가 있었다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int[][] map = new int[5][5]; static int[] dr = {-1,1,0,0}; ..
[백준] 16652 Binary tree - Java
[백준] 16652 Binary tree - Java
2022.08.06이진트리니까 트리를 입력받을 때 노드 클래스를 이용해 left와 right를 설정해 주는 방법으로도 풀 수 있지만 간단하게 그래프로 바라보고 풀었다. dfs를 돌리며 높이를 적당히 조절해 주면 된다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int root; static ArrayList[] list; static int N; static boolean visit[]; static int[] arr; static int cnt; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedRead..
[백준] 16652 Email Destruction - Java
[백준] 16652 Email Destruction - Java
2022.08.06Re : 접두사가 달린 이메일 이름은 몇 번이고 삭제될 수 있기에 삭제될 수 있는 최소 개수를 구해 입력받은 n과 비교해야 한다. Re : 는 띄어쓰기를 포함해서 4글자이니, LastIndexOf 메서드를 사용해 Re가 몇 번 나왔는지 계산해줬다. import java.util.*; import java.io.*; import java.math.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readL..
[백준] 10895 Great Pow! - Java
[백준] 10895 Great Pow! - Java
2022.08.05종이에 써 가며 하나하나 작성해보면 규칙이 보인다. a가 1 일때의 답은 1 k가 0 일때의 답은 a k가 0이 아니면서 a가 짝수일 때의 답은 1 k가 0이 아니면서 a가 홀수일 때의 답은 a import java.util.*; import java.io.*; import java.math.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int a = Integer.parseI..
[백준] 2146 다리 만들기 - Java
[백준] 2146 다리 만들기 - Java
2022.07.311. 섬 마다 구역을 나눈다. (1, 2, 3...) 2. 완전탐색으로 건설할 수 있는 최소 길이의 다리를 구한다. - 구역을 나눌 때 ArrayList를 사용했는데, 더 좋은 방법이 있을 것 같다 - bfs함수를 2개 만들어서 사용했는데, 하나로 통일해서 풀 수 있을 것 같다. import java.util.*; import java.io.*; public class Main { static int N; static int[] dr = {-1,1,0,0}; static int[] dc = {0,0,-1,1}; static int[][] map; static boolean visit[][]; static int min =Integer.MAX_VALUE; static ArrayList island; pub..
[백준] 2583 영역 구하기 - Java
[백준] 2583 영역 구하기 - Java
2022.07.29격자가 행렬로 구성되어있지 않고 수능 수학에서 많이 보던 x y격자로 구성되어있다. 이에 따라 입력받을 때 주의해야하고, 이거 말고는 그냥 bfs돌리면 된다. import java.io.*; import java.util.*; public class Main { static int N, M, K; static int[][] map; static boolean[][] visit; static int[] dr = {-1,1,0,0}; static int[] dc = {0,0,-1,1}; static ArrayList list = new ArrayList(); static int cnt; static int total_cnt; public static void main(String[] args) throws ..
[백준] 2468 안전 영역 - Java
[백준] 2468 안전 영역 - Java
2022.07.28안전 영역의 정의를 제대로 알고 풀자. 안전 영역은 덩어리의 수이다. 안전 영역은 위와 같이 정의된다. bfs함수 만들고 인자를 하나씩 늘려가면서 풀자. import java.io.*; import java.util.*; public class Main { static int N; static int[][] map; static int max; static int highest; static int[] dr = {-1,1,0,0}; static int[] dc = {0,0,-1,1}; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(Syst..
[백준] 25332 수들의 합 8 - Java
[백준] 25332 수들의 합 8 - Java
2022.07.28두 수열의 길이가 왜 같을까? 이 부분을 잘 생각해보자.. 길이가 같은 두 수열을 입력받고, 두 수열의 값을 뺀 값을 가지는 새로운 수열을 정의하자. 새로 만들어진 수열에 대해 누적 합 배열을 구하고, 이 배열의 구간합이 0인 부분수열의 수를 구하자. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int N = Integer.parseInt(b..
[백준] 2015 수들의 합 4 - Java
[백준] 2015 수들의 합 4 - Java
2022.07.28이중 for문을 돌면 당연히 시간 초과가 난다 -_- 먼저 입력받은 수들에 대해 누적 합 배열을 만들고 시작한다. 해시 맵은 누적 합 배열을 돌면서 해당 값이 나온 횟수를 저장하고, 현재 값 - 목표 값을 확인해 답을 갱신할 때 사용한다. 일단 누적 합 배열을 만들어놓으면 sum_arr[6] - sum_arr[3] == arr[4] + arr[5] + arr[6] 이렇게 사용할 수 있으니.. 누적 합 배열을 돌면서 배열의 값이 찾으려는 값과 같으면 ans 1 증가. 나머지는 위에서 설명한 대로. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ B..
[백준] 25395 커넥티드 카 실험 - Java
[백준] 25395 커넥티드 카 실험 - Java
2022.07.28bfs돌려서 푸는데.. 그냥 풀면 시간 초과가 발생한다. 커넥티드 카 들의 위치를 기준으로 정렬해 처음으로 도달할 수 없는 커넥티드 카를 만나면 break;로 탈출해 빠르게 탐색하도록 했다. 나머지 내용은 그냥 bfs import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.r..