Algorithm
[백준] 3980 선발 명단 - Java
[백준] 3980 선발 명단 - Java
2022.08.17재귀의 basis 조건은 11명을 모두 뽑았을 때이다. 선수의 능력치가 0이 아니면 뽑고, 백트래킹을 돌려서 모든 경우를 탐색하자. 백트래킹은 정말 많이 풀어봐야 한다. 개념은 알지만 활용하는게 쉽지 않은 단원.. import java.util.*; import java.io.*; import java.math.*; public class Main { static int TC; static int[][] map; static boolean[] visit; static int ans; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws Exception { BufferedReader br = ..
[백준] 1325 효율적인 해킹 - Java
[백준] 1325 효율적인 해킹 - Java
2022.08.14시간 제한이 좀 까다롭다. 최대한 시간을 줄여야 한다. bfs로 작성했는데.. 그냥 출력하면 시간초과가 발생한다. StringBuilder로 출력을 최대한 줄여야 한다. import java.util.*; import java.io.*; import java.math.*; public class Main { static ArrayList[] list; static int N, M; static int max = 0; static ArrayList ans_list = new ArrayList(); public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader..
PICNIC - Java
PICNIC - Java
2022.08.13백트래킹 시 같은 경우를 중복해서 세고 있을 때 각각의 경우에 순서를 부여해 중복을 제거할 수 있다. 여기서는 사전순으로 가장 먼저 오는 답 하나만 세도록 작성했다. 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(); int TC = Integer.parseInt(br.readLine()); while(--TC >= 0){ StringTokenize..
[백준] 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..
최소 신장 트리
최소 신장 트리
2022.07.29그래프에서 일부 간선을 선택해서 만든 트리를 신장 트리 (Spanning Tree)라고 한다. 트리라서 사이클이 있으면 안되니 n개의 정점이 있으면 정점을 모두 잇는 트리의 간선은 n-1개이다. 최소 신장 트리는 신장 트리에서 간선에 가중치가 있다고 할 때 가중치의 합이 최소인 트리를 말한다. 활용 분야는 통신, 회로 등 여러 군데가 있을 수 있고 생각해보면 더 많이 있을 것 같다.. 하지만 나한테는 활용 분야보다 최소 신장 트리를 활용하는 알고리즘 문제가 나온다는거다. 가중치가 있는 그래프가 주어졌을 때 최소 신장 트리를 어떻게 구할 수 있을까? 최단 거리를 구할 때 사용하는 알고리즘인 크루스칼, 프림 알고리즘을 사용할 수 있다. https://chanhuiseok.github.io/posts/algo..
[백준] 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 ..