본문 바로가기

전체 글103

백준 4963번 섬의 개수 JAVA 간단한 문제였다. BFS를 사용하면 된다. 이문제 이전에는 BFS에 대한 개념이 약했는데 이번에 확실히 깨달았다. import java.io.*; import java.lang.reflect.Array; import java.util.*; class XY{ int x; int y; XY(int x,int y){ this.x=x; this.y=y; } } public class Main { static int[][] map; static List answer = new ArrayList(); static int[][] visted; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader.. 2020. 9. 28.
백준 1520번 내리막길 JAVA 처음에는.. 톡방에서 이야기 했다시피 완전탐색으로 풀었는데..잘 생각해보니 탐색을 해야하는 맵의 크기가 500*500 으로 25만이어서.. 그걸 N^2으로 풀게되면 굉장히 끔찍한 결과가 나오게 된다. 후....아무리 생각해도 DP로 풀 방법이 떠오르지 않아 함께 스터디 하는 두분의 코드를 적극 참조하였다.. 감사합니다 두분.. 그리고 두분 코드를 참조하여서 다음부터는 4방향을 확인하는 코드는 dx,dy를 만들어서 for문으로 만들도록.. 아무튼 기본적으로는 DFS로 깊이로 들어가야 한다. BFS로는 안되는 이유가 우선 백트래킹이 불가능하다. 동일한 경로를 다시 방문할 확률이 있기 때문에 완전탐색이 되게 되는데 그렇게 된다면 처음 얘기했던 끔찍한 시간 복잡도가 나타나게 된다. 근데 DFS로 동일한 경로의 .. 2020. 9. 21.
백준 11060번 점프점프 JAVA 별로 어려운 문제는 아니었는데 방문하지 않은 경우에 대해서 예외처리를 하지 않아서 계속 틀렸다.. 문제의 핵심은 여느 DP가 그랬듯이 이전에 저장된 값을 이용해 비교하는 것 이다. 시간 복잡도는 배열의 개수 N개와 점프가 가능한 경우의 수들의 합인 M번을 반복해 O(NM)이 걸린다. import java.io.*; import java.util.Scanner; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N =.. 2020. 9. 21.
백준 18352번 특정 거리의 도시 찾기 JAVA 특정 거리의 도시 찾기 혼자선 못풀었는데 같은 스터디원의 아이디어를 참조하여 풀었다. Distance만 사용하면 되는 문제였고 이전의 거리 합+1 이 그 node에서의 거리인것을 인지를 못하고 풀어서.. 어제 꽤 오래 걸려서 풀었는데 다음부터는 이런실수 안하겠지..? import java.io.*; import java.util.*; import java.util.Collections; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String first = br.readLine.. 2020. 9. 17.

티스토리툴바