문제풀이64 백준 11479번 통나무건너뛰기 JAVA 해결 방식은 새로운 덱을 하나 만들어서 정렬시킨 배열에서 숫자가 큰 순으로 덱에다가 번갈아 가며 앞뒤로 집어넣으면 결론적으로 가장 작은 차이가 생기는 덱이 하나가 생성된다. 그 후, 덱에 들어있는 값을 배열로 옮겨 인접한 배열 요소의 차이가 가장 큰 값을 구한다. 단, 이때 그 차이는 절대값으로 해야한다. 한번에 맞춰서 기분이 좋다.. import java.io.*; import java.lang.reflect.Array; import java.util.*; import java.util.logging.FileHandler; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = n.. 2020. 11. 3. 백준 3273번 두수의합 JAVA 풀어보진 않았지만 전체 탐색으로 합을 구하려고 하면 아마도 복잡도가 N^2이 되어서 시간복잡도가 터질 가능성이 높은 문제이다. 문제의 핵심은 두수의 합이기 때문에 더한 값이 목표하는 값보다 크다면 그 뒷부분의 값은 더할필요가 없다는 것이 핵심이다. 가장 큰값과 작은 값을 시작과 끝점으로 삼아서 합이 작다면 시작부분을 더 큰수로 교체해주고 만약 더 크다면 끝부분을 더 작은수로 줄여주며 비교해주면서 일치하는 값이 나온다면 start를 증가시키거나 end를 줄여주어서 필요없는 부분은 탐색하지 않도록 한다. import java.io.*; import java.util.*; public class Main { static int[] numbers; public static void main(String[] ar.. 2020. 10. 11. 백준 14888번 연산자끼워넣기 JAVA 백트래킹을 이해했다면 어렵지 않은 문제다. 백트래킹은 기본적으로 dfs에서 깊이를 들어가다가 깊이 끝까지 들어가면 리턴해서 stack에서 pop하고 거기서 다른 선택지가 있다면 다시 그곳을 탐색해서 전체 탐색을 하는 방식이다. 연달아 두문제를 푸니까 이제 좀 감이 오는 느낌.. import java.io.*; import java.util.*; public class Main { static int[] numbers; static int MAX=-999999999; static int Min=999999999; static int n; public static void dfs(int[] opers, int sum,int point){ if(point==n){ MAX=Math.max(MAX,sum); Mi.. 2020. 10. 11. 백준 2239번, 2580번 JAVA 하하하핳 백트래킹으로 잘 풀면된다. 예제가 맞는데 틀렸던 이유는 return 조건을 예제에 맞춰서 51일시에 true를 리턴해버려서 발생한 어처구니 없는 실수였다.. 백트래킹을 이제야 제대로 이해한듯 하다. 핵심은 재귀는 결국은 스택인데 만약 조건을 만족시키지 못하면 이전 스택으로 돌아가서 List에 저장된 요소(숫자가 채워져있지 않는 부분)을 다시 체크하면서 다시 스택을 쌓아가고 모두 풀었으면 true를 반환해서 스택을 모두 스킵해버린다. 2239번과 2580번은 단순히 입력과 반환을 어떻게 하느냐의 차이. import java.io.*; import java.util.*; class XY{ int x; int y; XY(int x, int y){ this.x=x; this.y=y; } } public.. 2020. 10. 10. 이전 1 ··· 10 11 12 13 14 15 16 다음