728x90 코딩테스트22 [백준 14888] 연산자 끼워넣기 [java] 두 개의 배열에 각각 숫자와 연산자를 저장한다 dfs메소드를 재귀함수로 호출할 건데 매개변수로 하나는 현재 연산된 값과 현재 나온 숫자의 개수를 넘겨준다. 예를 들어) 5,6을 숫자로 입력하고 0,0,1,0이 연산자로 입력되면 처음에 5와 1(index)을 매개변수로 넘겨주고 index와 입력받은 숫자의 개수가 같지 않으면 for문을 이용해 연산자 배열을 순서대로 확인한다. 그래서 다음 매개변수는 5*6인 30과 2가 넘어가게 된다. 코드 package baekjoon; import java.util.Scanner; public class operator_embed { public static int MAX = Integer.MIN_VALUE; public static int MIN = Integer.M.. 2021. 5. 12. [백준 15652] N과 M (4) [java] 이 문제의 핵심은 비내림차순으로 출력해야 한다는 점이다. 즉, 처음 나온 숫자보다 큰거나 같은 수가 옆에 나와야 한다는 것이다. dfs방법으로 문제를 풀건데 원리는 간단하다. 만약 4 4를 입력받은 경우, 우선 가장 처음 나올 수 있는 수는 1 1 1 1 그다음에 나오는 수는 1 1 1 2 그다음은 1 1 1 3 이렇게 만들 수 있다. 쉽게 풀어보자면 배열의 길이를 depth로 보는 것이다. 즉 배열을 끝까지 다 채우면 depth를 만족시키고 return시키는 것이다. return된 다음에는 마지막 1이 들어간 부분만 2로 바꿔주면 된다. 지금까지 설명한 방법은 N과 M(3)을 푸는 방법이다. N과 M(4)에는 비내림차순이라는 조건이 추가됐는데 이것은 dfs를 호출할 때 현재 내 앞에 숫자를 알고 그 숫.. 2021. 5. 12. [백준 11725] 트리의 부모 찾기 [java] dfs를 이용하여 루트 노드부터 차례대로 아래로 내려가면서 문제를 해결한다. - 1번이 루트노드로 정해졌으므로 1번부터 밑으로 내려가면 된다 - 리스트를 만들어 서로 연결된 노드들을 넣어준다. - dfs 메소드에서 for문을 이용해 차례대로 노드들을 뽑아준다. - 뽑은 노드들을 다시 dfs로 후출하면 된다. * 위에서부터 차례대로 노드를 찾아가므로 부모배열을 만들고 dfs의 매개변수랑 연결된 값의 부모는 매개변수가 된다. 코드 package baekjoon; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class find_treeparent { static int n; static List[] lis.. 2021. 5. 6. [백준 9370] 미확인 도착지[java] 이 문제는 처음에는 무조건 지나야하는 점들을 방문하며 풀려했었다. 하지만 그러면 dijkstra알고리즘을 너무 많이 사용하게 되는거 같아서 다른 방법을 찾아봤다. 방법을 찾던 중 반드시 가야하는 곳의 가중치를 *2 +1을 해주면 홀수가 되고 나머지 가중치들은 *2만 한다면 결국 가여하는 길을 지나서 목적지에 도달한다고 생각할 때 목적지의 값은 홀수가 되있을 것이다. 결국 시작점에서 모든 노드로 가는 가중치들을 구하고 목적지로 예상되는 노드들의 가중치를 구했을 때 짝수인 경우를 출력해주면 된다. 코드 package baekjoon; import java.io.*; import java.util.*; public class uncomfirm_destination { static class Node imple.. 2021. 4. 8. [백준4386] 별자리 만들기 [java] 이 문제는 크르수칼 알고리즘과 union-find알고리즘으로 풀었다. 각 점들의 길이가 가중치가 되므로 모든 길이를 구한 뒤 그 길이를 오름차순으로 정렬시킨다 순서대로 가중치에 따른 시작점과 끝점을 보고 순환하게 되지 않는다면 결과값에 더해주면 된다. 코드 package baekjoon; import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; class Point1{ int num; double x; double y; Point1(int num, double x, double y){ this.num = num; this.x = x; this.y = y; } } cl.. 2021. 3. 31. [백준 9372] 상근이의 여행 [java] 이 문제는 간단한게 bfs문제로 풀면 가능한 문제다. 배열을 만들때 1부터 시작한다는 것만 생각해주면 된다! 코드 package baekjoon; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class sanggeun_travel { static int arr[][]; static boolean visit[]; static int country, line, result; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int i = 0; i 2021. 3. 31. 이전 1 2 3 4 다음 728x90
