동적 계획법
동적 계획법은 답을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 방법이다.
쉽게 말해 답을 재활용하는 것이다.
동적 계획법은 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한번만 계산하고 저장해둔 뒤 다시 한번 부분 문제를 이용할 때는 이 값을 바로 활용하는 방식으로 속도를 향상시킨다.
✅ 백준 11054
바이토닉 수열은 오름차순 부분 수열과 내림차순 부분 수열의 길이의 합으로 구할 수 있다. (겹치는 원소 떄문에 -1 해줘야 한다)
오름차순 부분 수열, 내림차순 부분 수열을 구하는 방식은 for문의 순회 방향만 다르고 같다.
static int LIS(int N){
// 탐색하지 않은 위치인 경우
if (r_dp[N]==null){
r_dp[N]=1;
//N 이전의 노드들을 탐색
for (int i=N-1; i>=0;i--){
if (seq[i]<seq[N]){
r_dp[N] = Math.max(r_dp[N],LIS(i)+1);
}
}
}
return r_dp[N];
}오름차순 부분 수열을 구하는 코드다.
동적계획법을 활용한다.
r_dp[N]은 N 까지의 오름차순 부분 수열의 길이를 의미한다.
만약 아직 해당 값을 구하지 않았다면 (null) 먼저 1로 초기화한다.
1로 초기화하는 이유는 자기 자신만 속한 부분배열은 모두 만족하므로 최소 길이가 1이기 떄문이다.
이전의 노드들에 대해 탐색한다.
seq[i]<seq[N]이면 오름차순 부분 배열의 조건을 만족한다.
따라서 재귀 호출을 통해 값을 구해준다. LIS(i)+1을 해주는 이유는 LIS(i)에 현재 N번쨰 원소까지 더해야 하기 떄문이다.
이미 LIS(N)의 값을 구해놓았을 경우 해당 값을 바로 리턴한다.
import java.util.Scanner;
public class Main {
static Integer[] r_dp;
static Integer[] l_dp;
static int[] seq;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
r_dp = new Integer[N];
l_dp = new Integer[N];
seq = new int[N];
for (int i=0; i<N; i++){
seq[i] = in.nextInt();
}
for (int i=0; i<N; i++){
LIS(i);
LDS(i);
}
int max = -1;
for (int i=0; i<N; i++){
max = Math.max(r_dp[i]+l_dp[i],max );
}
System.out.println(max-1);
}
static int LIS(int N){
// 탐색하지 않은 위치인 경우
if (r_dp[N]==null){
r_dp[N]=1;
//N 이전의 노드들을 탐색
for (int i=N-1; i>=0;i--){
if (seq[i]<seq[N]){
r_dp[N] = Math.max(r_dp[N],LIS(i)+1);
}
}
}
return r_dp[N];
}
static int LDS(int N){
if (l_dp[N]==null){
l_dp[N]=1;
for (int i=N+1; i<l_dp.length; i++){
if (seq[i]<seq[N]){
l_dp[N] = Math.max(l_dp[N], LDS(i)+1);
}
}
}
return l_dp[N];
}
}전체 코드는 위와 같다.
✅ 백준 2565
철거되어야 할 전선의 최소 개수 = 전체 전선 개수 - 겹치지 않고 설치 가능 최대 개수
라는 아이디어로 쉽게 풀 수 있다. 즉 겹치지 않고 최대한 설치 가능한 개수를 구하면 된다.
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[][] elec;
static Integer[] dp;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
elec = new int[N][2];
dp = new Integer[N];
for (int i=0; i<N; i++){
elec[i][0] = in.nextInt();
elec[i][1] = in.nextInt();
}
// 람다식을 사용해 전봇대 A 기준으로 정렬
Arrays.sort(elec, (arr1,arr2)->arr1[0]-arr2[0]);
int max = 0;
for (int i=0; i<N; i++){
max = Math.max(recur(i),max);
}
System.out.println(N-max);
}
public static int recur(int n){
if (dp[n]==null){
dp[n]=1;
for (int i=n+1; i<dp.length; i++){
if (elec[n][1]<elec[i][1]){
dp[n] = Math.max(dp[n],recur(i)+1);
}
}
}
return dp[n];
}
}전체 코드는 위와 같다.
elec는 전깃줄을 나타내는 2차원 배열이다
dp는 동적프로그래밍에 활용할 배열이다
전깃줄을 먼저 입력받고
A전봇대를 기준으로 정렬한다.
Arrays.sort(elec, (arr1,arr2)->arr1[0]-arr2[0]);
람다식을 활용해 Comparator를 구현한다.
각 i 자리별 최대 전깃줄 설치 개수를 구한다.
recur에서는 dp[n]==null이면 dp[n]=1로 초기화한다.
A전봇대의 n번째에서 B전봇대로 뻗은 위치 elec[n][i] 보다 elec[i][1]이 더 크다면 전깃줄을 설치할 수 있는 것이다. dp[n] = Math.max(dp[n], recur(i)+1)로 dp[n] 값을 업데이트한다.
✅ 백준 9251
입력으로 주어진 두 문자열의 LCS의 길이를 구하는 문제이다.
LCS는 최장 공통 부분 수열이다.
LCS를 구하는 방법을 이해하고 점화식을 세워서 DP로 풀어야 한다.
나는 LCS를 구하는 방법도 잘 모르겠어서 헤메다가 풀이를 봤다.
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static char[] str1;
static char[] str2;
static Integer[][] dp;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
str1 = in.next().toCharArray();
str2= in.next().toCharArray();
dp = new Integer[str1.length][str2.length];
System.out.println(LCS(str1.length-1,str2.length-1));
}
static int LCS(int x, int y){
if (x==-1 || y==-1){
return 0;
}
// 탐색하지 않은 인덱스라면
if (dp[x][y]==null){
dp[x][y] = 0;
if (str1[x]==str2[y]){
dp[x][y] = LCS(x-1,y-1)+1;
}
else {
dp[x][y] = Math.max(LCS(x-1,y),LCS(x,y-1));
}
}
return dp[x][y];
}
}전체 코드는 위와 같다.
핵심은 새로 추가되는 str1[x]==str2[y] 라면 dp[x][y]=LCS(x-1,y-1)+1이라는 것과, 아닐 경우 dp[x][y] = Math.max(LCS(x-1,y),LCS(x,y-1)이라는 것이다.
