알고리즘

풀이 1) 문제의 입력값 범위가 -2^62 ~ 2^62 까지이므로 배열의 타입은 Long 으로 설정한다. 2) Arrays.sort() 로 정렬을 한다. 3) 주어지는 입력값이 1개일 수 있으므로 초기값은 ary[0]으로 잡는다. 4) ary[i].eqauls(ary[i+1])로 가장 많이 들고 있는 정수 카드를 찾는다. 배워가는 것 //getOrDefault //지정된 키가 매핑된 값을 반환하거나, 매핑이 없는 경우 defaultValue를 반환한다. //중복 카드 수가 늘어나면 +1을 한다. map.put(key, map.getOrDefault(key, 0)+1); 1번(정렬) import java.io.BufferedReader; import java.io.IOException; import jav..

풀이 1) 학생들의 각 과목 점수를 배열에 저장한다. or Student 클래스를 만들어 저장한다. 2) 문제의 조건에 맞게 Arrays.sort(ary, Comparator())를 이용해 정렬한다. (오름차순인지 내림차순인지 유의해야 함!) 3) 문자열 정렬은 a.compareTo(b) 를 사용한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Collections; import java.util.StringTokenizer; public class Main { static String ary[][]; ..

풀이 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 값이..