java
-
백준 15686 치킨 배달 - 조합, 백트레킹코테 풀이 2024. 2. 7. 16:47
이 문제는 백트레킹을 이용해 조합을 구현하고 차근히 조건을 생각하며 풀면 풀리는 문제다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.StringTokenizer; public class Main { //조합 구현 코드 public static ArrayList combination(ArrayList storeList, int m){ ArrayList ans = new ArrayList(); ArrayList..
-
소프티어 - 순서대로 방문하기(백트레킹)알고리즘 2024. 1. 30. 17:35
처음에는 dfs를 사용하여 stack을 사용해 풀려고 했으나 중복 제거를 처리하지 못해 풀지 못했다. 서로 다른 경우의 수를 구할 때는 백트레킹을 이용해서 풀어보자! 백트레킹은 재귀를 이용해 방문하고 방문 처리한 곳을 다시 취소하는 방법으로 거슬러 올라간다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class OrderVisit { static int[] x_move = {1,0,-1,0}; static int[] y_move = {0,1,0,-1}; //내가 방문한 target의 이전 순서는 다 방문했고, ..
-
java로 조합 구현알고리즘 2024. 1. 20. 14:04
import java.util.ArrayList; public class C { public static ArrayList combination(int[] nums , int k){ ArrayList ans = new ArrayList(); ArrayList curr = new ArrayList(); boolean[] used = new boolean[nums.length]; int start = 0; backtrack(start, nums, k, ans, curr, used); return ans; } public static void backtrack(int start, int[] nums, int k, ArrayList ans, ArrayList curr, boolean[] used) { if(cu..
-
java로 순열 구현알고리즘 2024. 1. 20. 13:31
import java.util.ArrayList; public class P { public static ArrayList p(int[] nums) { ArrayList ans = new ArrayList(); ArrayList curr = new ArrayList(); boolean[] used = new boolean[nums.length]; backtrack(curr, nums, ans, used); return ans; } public static void backtrack(ArrayList curr, int[] nums, ArrayList ans, boolean[] used){ if(curr.size() == nums.length) { //curr는 참조변수이기 때문에 변경될 때마다 결과 리스트..
-
백준 - 16236번 아기상어코테 풀이 2024. 1. 19. 12:19
이 문제는 여러 조건들을 만족시키는 메소드를 기능 별로 분리해 만들어야 헷갈리지 않는다. 이 문제의 핵심은 "거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다." 를 어떻게 처리하느냐다. 나는 기능 별로 두가지 메소드로 나누었다. 1. bfs 메소드 : 다음에 먹을 가장 적절한 물고기의 위치와 거기로 가는데 걸린 시간 반환 2. move 메소드 : bfs 메소드를 호출해서 물고기를 먹고 time을 업데이트하는 재귀함수 나는 핵심 조건을 bfs 메소드에서 PriorityQueue를 이용해 처리했다. PriorityQueue queue = new PriorityQueue(new Comparator() { @Override public i..
-
백준 7562번: 나이트의 이동코테 풀이 2023. 12. 18. 20:46
이 문제는 4 * 4 체스판을 직접 그려보고 한 시작점에서 모든 칸을 몇 칸 안에 도달할 수 있는지 직접 구해본다면 접근 방법을 찾을 수 있다. 다음은 4 * 4 체스판의 (0,0)에서 출발 했을 때 모든 칸에 도달하는 최소 이동 횟수다. 만약 (3,2) 칸에 몇 번만에 도달하는지 알고 싶다면 체스판을 그래프화 하여 graph[3][2]의 값을 구하면 된다. 다음은 손 코딩으로 흐름을 나타낸 것이다. 다음은 정답 java 코드이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWri..
-
백준 2579번: 계단 오르기코테 풀이 2023. 12. 17. 17:26
이 문제는 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 문제이다. 최댓값 구하는 문제는 DP 유형을 한번쯤 떠올려보길 바란다. 이 문제의 키포인트는 두가지이다. 1. n번째 계단에 도달할 수 있는 경우는 이 두가지 경우뿐이다. n-2번째 계단에서 2칸 점프해서 n번째 계단으로 오거나, n-3번째 계단에서 2칸 점프해서 n-1, n번째 계단으로 오거나. -> 따라서 점수는 n-2번째 계단까지 값의 최댓값 + n번째 계단값이나 n-3번째 계단까지 값의 최댓값 + n-1번째 계단값+ n번째 계단값 중 더 큰 값이다. 2. 계단의 개수가 2개 이하일 경우 base case를 만들 때 예외가 발생하므로 조건을 넣어서 처리해야한다. import java.io.Buff..
-
DP(동적 계획법)알고리즘 2023. 12. 17. 16:08
ex) 최대, 최소, 방법의 개수, 미래의 계산이 앞선 계산 결과에 영향을 받을 때 (1) 크고 복잡한 문제를 하위 문제로 나눈다. (2) 하위 문제에 대한 답을 계산한다. - 중복 하위 문제 - 계산 결과를 저장해서 중복된 문제에 사용 (3) 하위 문제에 대한 답으로 원래 문제에 대한 답을 계산한다. 상향식(bottom-up) 방법 - 반복문 public class DynamicProgrammingExample { // 다이나믹 프로그래밍을 활용한 피보나치 수열 계산 public static int fibonacci(int n) { int[] dp = new int[n + 1]; // 초기값 설정 dp[0] = 0; dp[1] = 1; for (int i = 2; i