728x90 코딩테스트22 [백준2606] 바이러스 [java] 이 문제는 dfs나 bfs나 상관없다고 생각하지만 bfs를 사용하면 큐를 이용해야 할 것 같아서 dfs를 사용했다. 트리를 표현하기 위해서 연결리스트방법을 사용했다 리스트안에 리스트를 넣어서 연결된 노드들을 표현했다. 또한 1부터 시작하므로 리스트에 크기를 1~주어진 크기보다+1을 해줬다. 코드 package baekjoon; import java.util.ArrayList; import java.util.Scanner; public class virus { public static ArrayList list[]; public static boolean check[]; static int cnt = 0; public static void main(String[] args) { Scanner scan = .. 2021. 3. 22. [백준1260번] DFS와 BFS 간단하게, 깊이우선탐색(DFS) 는 한 노드의 관해서 깊게 들어가면 된다. 따라서 한 노드를 방문했었는지를 기록하며 그 노드와 연결된 노드를 기준으로 다시 DFS메소드를 호출하면 된다. 너비우선탐색(BFS)는 한 노드에서 연결된 모든 노드를 방문하는 것이므로 큐를 이용하여 큐에서 빼낸 노드와 연결되며 방문하지 않은 모든 노드를 큐에 넣고 큐가 빌때까지 반복해주면 된다. 코드 package baekjoon; import java.util.*; public class dfs_bfs { public static boolean[] check; public static ArrayList list[]; public static void main(String[] args) { Scanner scan = new Sca.. 2021. 3. 18. [백준10989] 수 정렬하기 - 3 [java] 이 문제는 수 정렬하기 3번째 문제인 만큼 더 생각해야할 부분이 있다. 바로 데이터의 양이 너무 많다는 것이다!! 따라서 Scanner를 사용해서는 문제를 통과할 수 없고 BufferedReader를 사용해야 한다. Scanner와 BufferedReader의 차이는 값을 입력받을 때 buffer로 한번에 통과시키면 많은 데이터를 받을 때 훨씬 빠르게 처리할 수 있다. 또한 배열과 리스트에서도 데이터를 처리할 때 차이가 많이 나게 된다. 따라서 같은 sort이고 Arrays.sort가 시간복잡도가 높고 Collection.sort가 시간복잡도가 작더라도 이 문제처럼 주어진 데이터가 많을 때는 Arrays.sort를 쓰는게 더 좋다. 따라서 Arrays.sort와 BufferedReader를 사용하면 문제.. 2021. 3. 10. [백준2751] 수 정렬하기-2 [java] 2751번 수 정렬하기 2번문제인데 앞의 문제인 2750문제보다 수의 범위가 훨씬 넓어졌다. 따라서 코드에 대해 좀 더 정교한 필요하다. 예를 들어 2750번에서는 가능했어 Arrays.sort를 사용하면 시간초과가 발생한다. 여기서 약간의 정리를 하자면 Arrays.sort()의 경우에는 dual-pivot quicksort 알고리즘을 사용한다. quciksort가 평균 시간복잡도 o(nlogn)으로 좋은 알고리즘이긴 하지만 최악의 경우에는 o(n^2)이라는 것을 알아야한다. 또한 이 문제에서는 일부러 최악의 경우를 배치시켜 시간초과 문제가 발생하도록 했다. 위의 문제를 해결하기 위해서는 Collections.sort()라는알고리즘을 사용해야 한다. 이 알고리즘은 반복합병 및 삽입 알고리즘을 사용하는데.. 2021. 3. 8. 이전 1 2 3 4 다음 728x90
