알고리즘/동적프로그래밍(DP)42

• 

  [백준] 1937번: 욕심쟁이 판다 - java 만약 모든 칸에서 DFS 탐색을 한다면 매 칸에서 최대 n^2만큼 이동할 수 있다. 따라서 n^2의 칸에서 n^2 만큼의 탐색을 한다면 O(n^4) 로 시간 복잡도가 터져버릴 것이다. 따라서 DP를 이용해서 이미 DFS 를 탐색한 칸에 대해서는 값을 저장해서 탐색 횟수를 줄여야 한다. dp => 해당 칸에서의 최장 경로를 저장해둔 것이다. 즉, 다른 칸(a)에서 탐색을 하다가 이미 방문한 칸(b)을 탐색하게 된다면, b에서 계속해서 탐색을 할 필요가 없이, b칸에 저장되어 있는 dp값을 더하기만 하면 된다. dp[i][j] => 판다가 (i,j) 에서 출발할 때 최대로 이동할 수 있는 칸 수 를 의미한다. 1) 모든 칸에서 탐색 시작 2) DFS 탐색 상 하 좌 우를 탐색하며, 현재 칸 보다 다음칸에 더.. 알고리즘/동적프로그래밍(DP) 2023. 3. 21.

• 

  [swea] 최적 경로 - java BruteForce - 순열 처음 푼 풀이... 그냥 단순하게 고객 N명을 방문할 순서를 순열로 만들어서, 해당 순서대로 이동거리를 구해보고, 이동거리가 최소값이라면 갱신하는 방법을 사용하였다. 이는 N이 최대 10이기 때문에 10! = 3628800 로 해결할 수 있는 문제였다. 해당 문제는 시간제한이 20초로.. 없으나 다름없는 문제라 정답으로 인정되긴 했지만, 다른 아이디어로 더 빠르게 풀어보고 싶어졌다. import java.awt.Point; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.Outp.. 알고리즘/동적프로그래밍(DP) 2023. 2. 22.

• [백준] 14722번: 우유 도시 - java 나의 풀이 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.LinkedList; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; import java.util.Stack; import java.util.StringTokenizer; public class Main { static BufferedReader b.. 알고리즘/동적프로그래밍(DP) 2023. 2. 20.

• 

  [백준] 1633번: 최고의 팀 만들기 - java 문제설명 나의코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static Stri.. 알고리즘/동적프로그래밍(DP) 2023. 2. 15.

• 

  [백준] 14852번: 타일 채우기 3 - java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; static final int MOD = 1000000007; static long[][] dp = new long[1000001][2]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); // dp[n]=2* dp[n-1.. 알고리즘/동적프로그래밍(DP) 2023. 2. 10.

• [백준] 13910번: 개업 - java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashSet; import java.util.Set; import java.util.StringTokenizer; public class Main { static int n; static final int MAX = 10001; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 알고리즘/동적프로그래밍(DP) 2023. 2. 9.

• 

  [백준] 2565번: 전깃줄 - java 문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남아있는 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전.. 알고리즘/동적프로그래밍(DP) 2023. 2. 8.

• [백준] 1106번: 호텔 - java 문제 세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다. 형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다. 예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다. 각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기.. 알고리즘/동적프로그래밍(DP) 2023. 2. 8.

• [백준] 21317번: 징검다리 건너기 - java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int[][] rock = new.. 알고리즘/동적프로그래밍(DP) 2023. 2. 4.

• 

  [백준] 11660번: 구간 합 구하기 5 - java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static long mod = 1000000000; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.ne.. 알고리즘/동적프로그래밍(DP) 2023. 2. 4.

• [백준] 1890번: 점프 - java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[][] arr = new int[n][n]; long[][] dp = new long[n][n]; for (int i = 0; i < n; i++) { String[] input = br.r.. 알고리즘/동적프로그래밍(DP) 2023. 2. 2.

• 

  [swea] 3282번: 0/1 Knapsack - 파이썬(python) 처음엔 백트래킹으로 문제를 풀었는데, 제한시간 초과로 실패하게 되었다. 백트랙킹의 경우 보통 시간 복잡도가 2^n 에 근접하다. 따라서 n이 20이하인 경우에만 백트래킹을 사용해야 한다. 이 문제의 경우 n=100 이므로, 2^100은 당연히 시간초과를 일으킬 것이다.... 따라서 dp를 사용하자! dp[i][j] 에서 i는 i번째 물건까지 선택할 수 있음을 뜻하고, j는 j무게까지 물건을 담을 수 있음을 뜻한다. 현재 물건무게가 j 보다 크다면, 해당 물건을 선택할 수 없으므로 [이전 물건][같은 무게] (dp[i-1][j]) 를 입력해준다. 현재 물건무게가 j이하라면, 둘 중 더 큰 값을 선택한다. 현재 물건을 넣어준다. 현재물건가치 + knapsack[i-1][j-weight] (이전물건, j-현재.. 알고리즘/동적프로그래밍(DP) 2022. 11. 12.