백준

[백준] 연속합 2 (!) (1932번 JAVA) / 401 - 다이나믹 프로그래밍 1 (연습) [접근 방법] 첫번째 방법 ) DP를 1차원 배열로 2가지 구성 Left -> Right (index : 0 -> n-1) 방향으로 연속합 DP1 배열 을 구성 Right -> Left (index : n-1 -> 0) 방향으로 연속합 DP2 배열 을 구성 index : i 의 원소를 제외하는 경우의 연속합 최댓값을 갱신하며 구한다. i 번째 원소를 제외한 연속합 = DP1[i-1] + DP2[i+1] 두번째 방법 ) DP를 2차원 배열로 구성 [JAVA 코드 - 첫번째 방법] import java.io.BufferedReader; import java.io.BufferedWriter; import java...

[백준] 가장 긴 바이토닉 부분 수열 (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..