알고리즘

풀이 1) dp 정의 - dp[n][k] : 각 무게에서 n번째 물건까지 담을 경우(담을 수 있는지 판별 후) 가질 수 있는 최대 가치를 저장 행 : n번째 물건 열 : 무게 k 2) 점화식 if(k - W[n] >= 0) // 담을 수 있다. dp[n][k] = Math.max(dp[n-1][k], V[n] + dp[n-1][k - W[n]]; else dp[n][k] = dp[n-1][k]; https://st-lab.tistory.com/141 https://fbtmdwhd33.tistory.com/60 1번 → Top-down 방식 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ..

풀이 1) dp 정의 - 입력받은 첫번째 문자열을 char_one[], 두번째 문자열을 char_two[] 라고 할 때 각각 i, j번째까지의 부분 수열 중, 공통되는 부분 수열을 찾아 그 중 제일 긴 것을 dp[i][j]에 저장한다. 2) 점화식 if(char_one[i] == char_two[j]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) https://st-lab.tistory.com/139 [백준] 9251번 : LCS - JAVA [자바] www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 ..

1-(1)번 - 본인(N)을 중심으로 0~N-1을 탐색하며 작은 값을 찾아, 가장 긴 증가하는 부분 수열을 찾는다. → Top-down 방식 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int[][] ary; //입력받은 수열을 담을 공간이다. static int[] dp; //증가하는 부분수열을 담을 공간이다. public static void main(String[] args) throws IOException { Buffered..

풀이 1) 1 - dp1[i] : ary[0]~ary[i-1] 까지 탐색을 하며 ary[i]보다 작은 값의 갯수를 저장한다. 2 - dp2[i] : ary[i]~ary[N] 까지 탐색을 하며 ary[i]보다 작은 값의 갯수를 저장한다. -> 증감을 파악하기 위해서 2) '가장 긴 증가하는 부분 수열' 문제와 같이 처음 dp1[N], dp2[N] == 0 (빈 값) 일 때, 자기 자신도 갯수에 포함해야 하므로 1로 초기화 한다. 3) dp1[N]을 구하는 함수에서는 1)-1 식을 코드로 dp2[N]을 구하는 함수에서는 2)-2 식을 코드로 작성을 한다. ex> dp1 for(int i=0;i

풀이 1) dp[i] : ary[0]~ary[i-1] 까지 탐색을 하며 ary[i]보다 작은 값의 갯수를 저장한다. 2) 식을 세워보면 for(int i=N-1;i>=0;--i){ if(ary[i] 제일 큰 값으로 유지해야 하므로 dp[0]~dp[N-1]까지 모두 구해주면 된다. 1번 → Top-down 방식 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] ary; //입력되는 수열의 값을 받는다. static int[] dp; //i번째 값보다 작은 값들을 저장하는 배..

풀이 - '2579번 계단오르기' 문제와 비슷하다. 계단 오르기와 마찬가지로 연속 3잔을 마실 수는 없다. 하지만 마지막 계단(잔)을 밟지 않아도 된다. 따라서 solve(N-2) + ary[N] vs solve(N-3) + ary(N-1) + ary[N] 비교에 이어 마지막 계단(잔)을 밟지 않는 경우인 dp[N-1] == solve(N-1) 과의 비교도 필요하다. 1번 → Top-down 방식 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int[] ary; //포두주 잔에 담긴 포도주의 양을 담는 배열이다. //포도주의 양이 0 값이..

처음에 자신있게 점화식을 f(N) = f(N-1) - fibo(N) 으로 세웠지만, 틀렸습니다.. ㅎㅎ 조건 - N자리 숫자의 계단수 개수를 출력하라. 풀이 - N자리 숫자의 각 value(0~9)가 가지는 계단수를 저장하고, => dp[N][value] 메모제이션 한 값을 활용한다. (개인적으로는 dp 구조를 생각하기 어려웠음) - 계단수를 만들기 위해서는, value가 0일 때는 1 / 9일 때는 8 / 이 외에는 value-1, value+1 두가지로 뻗칠 수 있다. https://st-lab.tistory.com/134 [백준] 10844번 : 쉬운 계단 수 - JAVA [자바] www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,..

1번 → Top-down 방식 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static Integer[] dp; //각 숫자별로 1로 만드는 연산 횟수의 최솟값을 저장한다. public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); //정수 N을 입력한다. dp = new Integer[N+1]; /..