DynamicProgramming

https://www.acmicpc.net/problem/14002 📌 자바(Java)로 푸는 가장 긴 증가하는 부분수열 4 - 백준 14002 📈최장 증가 부분 수열(LIS)을 구하고, 해당 수열을 출력하라!🔎 문제 개요 백준 14002번 - 가장 긴 증가하는 부분 수열 4 문제는기본적인 LIS(최장 증가 부분 수열) 문제에👉 “LIS 경로까지 출력”이 추가된 버전입니다.💡 예제 입력6 10 20 10 30 20 50 💡 예제 출력4 10 20 30 50 🛠 알고리즘 접근 방식 이 문제는 기본 LIS 문제에서“LIS의 경로를 저장”해야 하기 때문에✔ 단순한 DP 배열뿐 아니라✔ prev[] (이전 인덱스), lastIndex[] (길이별 마지막 인덱스) 추적이 필요합니다. 🔹 핵심..

https://www.acmicpc.net/problem/12852 📌 자바(Java)로 푸는 1로 만들기 2 - 백준 12852 🔢최소 연산 횟수 + 경로 추적까지 하는 DP 문제! 🔎 문제 개요 백준 12852번 - 1로 만들기 2 문제는정수 N이 주어졌을 때,1로 만들기 위해 사용할 수 있는 연산은 다음 세 가지입니다: X → X / 3 (3으로 나누어떨어질 때만)X → X / 2 (2로 나누어떨어질 때만)X → X - 1 최소 연산 횟수를 출력하고그 경로에 해당하는 숫자 순서도 출력해야 합니다. 💡 예제 입력10 💡 예제 출력310 9 3 1 🛠 알고리즘 접근 방식: Dynamic Programming (DP) ✏️ 핵심 전략 dp[i]: i를 1로 만들기 위한 최소 연산 횟수c..

https://www.acmicpc.net/problem/9252   두 문자열 간의 최장 공통 부분 수열(Longest Common Subsequence, LCS)을 구하는 문제다. LCS는 두 문자열에서 순서를 유지하면서 삭제 가능한 가장 긴 공통 부분 문자열을 의미한다.이를 동적 계획법(DP)을 사용하여 효율적으로 계산하고자 했다.먼저 두 문자열 s1과 s2를 입력받고, 두 문자열의 길이를 기반으로 DP 배열을 초기화한다. dp[i][j]는 문자열 s1의 첫 i글자와 s2의 첫 j글자 간의 최장 공통 부분 수열의 길이를 저장한다.DP 테이블을 채우는 과정에서, 현재 문자 s1.charAt(i - 1)와 s2.charAt(j - 1)이 같으면 dp[i][j]는 dp[i - 1][j - 1] + 1로 ..

https://www.acmicpc.net/problem/7579   이문제를 접했을때 어떤 알고리즘을 풀어야 할지 몰라 풀이방법을 찾아보니DP로 풀어야 함을 알 수 있었다. int[][] dp배열을 선언하고dp[i][j] 에서 i 는 i번째의 앱까지 고려하였을 경우를 의미하고j는 가능한 비용의 경우의 수를 의미한다.먼저 입력값을 받아 실행 중인 앱의 개수 N, 필요한 메모리 M, 각 앱의 메모리 사용량과 비활성화 비용을 각각 m과 c 배열에 저장한다.DP 배열은 비용의 최대값(10000)까지 고려할 수 있도록 초기화한다.DP 계산 과정은 각 앱을 순차적으로 처리하면서 진행된다.i번째 앱을 고려할 때, 현재 비용 j로 확보 가능한 메모리를 갱신한다. 만약 j가 c[i]보다 크거나 같다면,i번째 앱을 비활..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[][] board = new int[n + 1][3]; for(int i = 1; i

package BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseI..