[코딩테스트] Java - 동적계획법(Dynamic Programming)

동적계획법

- 동적계획법: 작은 부분 문제들을 해결하고 이를 활용하여 전체 문제를 해결하는 방법

- 동적계획법의 조건: 최적 부분 구조 + 중복 부분 문제

+) 최적 부분 구조: 작은 문제의 해결책의 합으로 큰 문제를 해결할 수 있는 구조

+) 중복 부분 문제: 큰 문제를 나누었을 때 작은 문제가 여러 개 반복되는 문제

 

(동적계획법 풀이법)

- 문제를 해결하는 해가 있다고 가정

- 종료 조건을 설정

- 점화식을 세움

 

(동적계획법 주요 기법)

- 재귀

- 반복문: 재귀문 대신 사용

- 메모이제이션: 재귀 호출의 횟수를 줄임

 

(최장 증가 부분 수열)

- 부분 수열: 주어진 수열 중 일부를 뽑아 새로 만든 수열. 각각의 원소는 전후 관계를 유지

- 최장 증가 부분 수열(Long Increasing Subsequence): 부분 수열의 원소가 오름차순을 유지하면서도 길이가 가장 긴 수열

- LIS 특징: 숫자가 점차 증가. 원소 간의 전후 관계 유지

 

(최장 공통 부분 수열)

- 최장 공통 부분 수열(Longest Common Subsequence): 두 수열이 특정 기준에 따라 양쪽에서 공통으로 발견할 수 있는 가장 긴 부분 수열

 

예제

(피보나치 수열)

- A[i+2] = A[i+1] + A[i]

class Solution {
    public static void main(String[] args) {
        int[] fibo = new int[10];

        for (int i = 0; i < fibo.length; ++i) {
            if (i <= 1) {
                fibo[i] = 1;
            } else {
                fibo[i] = fibo[i - 1] + fibo[i - 2];
            }
        }
        
        System.out.println(Arrays.toString(fibo));
    }
}

(LIS 길이 구하기)

- dp[N] = arr[N]을 마지막 원소로 하는 LIS의 길이

- 점화식1: dp[N] = max(dp[K]) + 1(1 <= K < N, arr[K] < arr[N])

- 점화식2: dp[1] = 1(종료조건)

 

- 입력: nums(정수 배열)

- 출력: LIS의 길이

import java.util.Arrays;

class Solution {
    private static int solution(int[] nums) {
        int n = nums.length;
        
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }
}

 

(LCS 길이 구하기)

- LCS 조건: 두 문자열의 특정 문자가 같은지. 같다면 찾은 두 문자의 위치가 이전에 찾은 문자의 다음에 있는지

- LCS(i, j) = x[1...i]와 y[1...j]의 LCS의 길이

- 점화식1: LCS(0, 0) = 0

- 점화식2: x[i] = y[j]이면 LCS(i - 1, j - 1) + 1

- 점화식3: x[i] != y[j]이면 max(LCS(i - 1, j), LCS(i, j - 1))

 

- 입력: str1(알파벳 대소문자로 된 문자열), str2(알파벳 대소문자로 된 문자열)

- 출력: 최장 공통 부분 수열의 길이

class Solution {
    private static int solution(String str1, String str2) {
        int m = str1.length();
        int n = str2.length();
        
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}