![]()
[백준] 가장 긴 바이토닉 부분 수열 (11054번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 1. LIS를 구한다. 2. LDS를 구한다. 3. LIS + LDS - 1를 하여 가장 긴 바이토닉 부분 수열 DP를 구한다. [JAVA 코드] import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main{ public static void main(String[] args) throws IOE..
![]()
[백준] 가장 긴 감소하는 부분 수열 (11722번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 을 아주 조금 비튼 문제이다. https://notorious.tistory.com/180 [백준] 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA) / 400 - 다이나믹 프로그래밍 1 [백준] 400 - 다이나믹 프로그래밍 1 : 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA) 최장 증가 부분 수열 이란...? (LIS : Longest Increasing Subsequence) : 어떤 임의의 수열이 주어질 때, 이 수열에서 볓개의 notorious.tistory.com 가장 긴 감소하는 부분 수열을 구하는 문제이다. DP를 갱신하는 조건 문을 바꾸기만 ..
![]()
[백준] 가장 큰 증가 부분 수열 (!) (11055번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] LIS 문제와 비슷하다곤 하지만, 나에겐 굉장히 어려운 문제였다. LIS는 DP 배열에 원소간의 대소 관계를 이용한 일종의 서열을 저장해 두었지만, 이번 문제에는 본인을 마지막으로 하는 증가 수열 중 가장 큰 수열원소의 합을 저장한다. 인덱스 4의 경우, [1, 2, 50]의 증가 부분 수열을 가지고 있다. 인덱스 5를 고려하기 위해서 DP의 인덱스 4에 이전 인덱스 중 가장 큰 수열원소의 합을 미리저장해 놓으면 편할 것이다. 완벽히 이해를 하지 못해 더이상의 설명은 어렵다. [JAVA 코드] import java.io.BufferedReader; import java.io.Bu..
![]()
[백준] 정수 삼각형 (1932번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 이 문제는 상당히 유명한 DP 활용 문제이다. 1. 삼각형의 cost를 2차원 배열로 정의 한다. 2. cost 배열의 원소를 누적합 중 최댓값으로 갱신한다. 3. n 열의 값 (총 경로의 cost 누적합) 중 최댓값을 도출한다. int max = 0; for(int i=1; i
![]()
[백준] 포도주 시식 (2156번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Buff..
![]()
[백준] 스티커 (9465번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] (0 , 0) 을 선택한다면, 선택 가능한 곳은 (1, 2) 와 (1, 3) 이다. ※ (1 , 3) 보다 뒤 쪽을 선택한다면 최대값을 만들 수 없다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main{ public static void main(String[] args) throws IOExcepti..
