DP

🔺 문제 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.util.*; import java.io.*; public class Main { static final int MOD = 10007; public static void main(String[] args) throws IOException {..

🔺 문제 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import java.util.*; import java.io.*; public class Main { static final int MOD = 9901; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); /..

🔺 문제 11052번: 카드 구매하기첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)www.acmicpc.net  🔺 코드123456789101112131415161718192021222324252627import java.util.*;import java.io.*; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader br = new Buffe..

🔺 문제 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import java.util.*; import java.io.*; import java.math.*; public class Main { public static void main(String[] args) throws IOException ..

🔺 문제 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.util.*; import java.io.*; public class Main { static int N; static int[] arr, dp; public static void ..

🔺 문제 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException..

📍 정의 및 특징 주어진 수열에서 증가하는 순서로 연속되는 부분 수열 중 가장 긴 길이를 구하는 문제 📍 LIS 실행 방법 1) DP 활용 → 시간 복잡도 : O(N^2) 2) 이분 탐색 활용 → 시간 복잡도 : O(N log N) 📍 필요 변수 ✔ DP / LIS 배열 🧩 1) DP를 활용한 LIS 실행 과정 : O(n^2) DP 테이블을 생성하여 각 원소를 마지막으로 하는 LIS의 길이 저장 초기값으로 모든 원소의 LIS 길이를 1로 설정 각 원소 i에 대해, 이전 원소 j(0 nums[j]인지로 판단) 만약 nums[i] > nums[j]라면, dp[i] = max(dp[i], dp[j] + 1) 수행 ⇨ i번째 원소를 마지막으로 하는 LIS의 길이 갱신 모든 i에 대해 위 과정을 반복하면, dp ..

📍 연속합 정의 주어진 수열에서 연속된 부분 수열의 합 중 최댓값을 구하는 문제 📍 해결 방법 ① DP ◾ WHEN? 입력 크기가 작은 경우 ◾ HOW? 이전 부분 수열의 합에 현재 수를 더하면서 최댓값 업데이트 (점화식 : 현재 수를 더할 것인지 or 현재 수부터 새로운 부분 수열을 시작할 것인지 결정) ② 투 포인터 ◾ WHEN? 입력 크기가 큰 경우 & 수열 순서가 중요한 문제 (수열의 순서를 유지하며 부분 수열을 구할 수 있으므로) ◾ HOW? 시작 포인터와 끝 포인터를 조정하면서 합을 계산하고, 최댓값 업데이트 ➕ 예제 [백준/JAVA] 1644번: 소수의 연속합 🔺 문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net..

📍 정의 및 특징 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제 - DP의 일종 - 문제 유형 : 최장 공통 부분 수열 길이 구하기, 최장 공통 부분 수열 구하기 #DP 📍 필요 변수 ✔ 2차원 LCS 배열 - LCS 길이 찾기용 ✔ 2차원 result 배열 - LCS 배열 결과값 저장용 📍 실행 과정 Case 1) 최장 공통 부분 수열 "길이" 찾기 /* LCS 길이 구하기 */ if(i == 0 || j == 0) LCS[i][j] = 0; else if (ch1[i] == ch2[j]) LCS[i][j] = LCS[i - 1][j - 1] + 1; else LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]) 문자열 A와 B를 한 ..