꿀잠

https://leetcode.com/problems/regular-expression-matching/description/

주어진 문자열이 패턴에 맞는 문자열인지 확인하는 문제이다. 주어지는 패턴은 '.' 일 경우 같은 모든 문자에 대칭 되고, '*' 일 경우 앞 글자 하나와 함께 묶여 해당 문자가 여러 개 가능하다는 뜻이다. DP로 해결이 가능하고 이전에 풀었던 다른 문제들의 경험 덕분에 풀 수 있었다. 아래의 두 문제와 점화식을 만들어 가는 방식이 비슷하다.

https://leetcode.com/problems/edit-distance/description/
https://ygs3004.tistory.com/97

https://leetcode.com/problems/longest-common-subsequence/description/
https://ygs3004.tistory.com/78

각 문자의 부분 문자열을 기반으로 DP 배열의 초기화와 점화식을 세워줄 수 있다. 특정 문자열 s의 인덱스 j 와 패턴 p의 문자열 i일 때를 생각해 보자. "." 또는 각 문자가 해당 인덱스에서 같을 경우 dp 배열의 true,false 값은 (i - 1)(j - 1)의 값과 같다. 왜냐하면 각 글자가 추가 되기 전에 같았다면 새로운 글자가 똑같이 생긴 경우이기 때문이다. 그리고 각 글자가 다를 경우 당연히 false가 된다.

별이 있는 패턴의 경우 해당 패턴의 i - 1 일 때의 값이 참인 경우에 참이 된다. 패턴의 새로운 문자열과 별개로 참이기 때문이다. 또한 j - 1 이 참일 경우 별문자의 문자값과 j의 문자값이 같을 경우 참이 된다. 그 이전까지의 문자가 패턴에 부합할 때 별 문자의 문자 새로 생겼다고 판단할 수 있기 때문이다. 아래에 임의의 값을 가지고 True, False 값을 찾아가는 배열을 만든 경우이다. i인 row가 늘어나는 경우를 패턴, j인 col이 늘어나는 경우가 문자열을 나타낸다.

확인해 보아야 하는 관계는 각 글자가 같을 때 (i - 1). (j - 1)의 값을 참조 해야 한다는 것, 별패턴일 경우엔 (i - 1)의 값과 문자가 같을 때 (j - 1)의 값을 참조 해야 한다는 점이다.

해당 규칙을 이용해서 최종적으로 통과한 코드는 아래와 같다. 별표의 경우 문자 + 별로 두 글자의 인덱스를 차지하므로 대문자로 치환하여 비교문을 작성했다.

public class Solution {  
    public boolean isMatch(String s, String p) {  
  
        final String dotStar = String.valueOf((char)('a' - 1));  
  
        // * + 문자를 대문자로, . 일 경우 dotStar로 치환(char < 'a'로 부등호로 비교하기 위하여)  
        while(p.indexOf("*") > - 1){  
            int starIdx = p.indexOf("*");  
            String starChar = String.valueOf(p.charAt(starIdx - 1)).toUpperCase();  
            starChar = starChar.equals(".") ? dotStar : starChar;  
            p = p.substring(0, starIdx - 1) + starChar + p.substring(starIdx + 1);  
        }  
  
        boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];  
        dp[0][0] = true;  
  
        for(int i = 1; i < dp.length; i++){  
            dp[i][0] = (p.charAt(i - 1) != '.') && (p.charAt(i - 1) < 'a') && dp[i - 1][0];  
        }  
  
        for(int i = 1; i < dp.length; i++){  
            char char1 = p.charAt(i - 1);  
            for(int j = 1; j < dp[0].length; j++){  
                char char2 = s.charAt(j - 1);  
                if(char1 == '.' || (char1 == char2)){  
                    dp[i][j] = dp[i - 1][j - 1];  
                }else if(char1 < 'a'){  
                    dp[i][j] = dp[i - 1][j] || (dp[i][j - 1]  
                            && (char1 == (char)('a' - 1) // dotStart일 경우  
                                || ((char1 + ('a' - 'A')) == char2))); // 대문자일 경우  
                }else{  
                    dp[i][j] = false;  
                }  
            }  
        }  
  
        return dp[p.length()][s.length()];  
  
    }  
  
}

https://leetcode.com/problems/word-break/description/

주어진 문자열을 주어진 사전 안의 있는 단어로 분해할 수 있는지 물어보는 문제이다.
최초 문제 풀이시 DFS로 시도하였으나 시간 초과가 발생하였다. DP 카테고리의 문제이므로 DP로 풀어볼 아이디어를 찾았다.

주어진 문자열을 한글자씩 늘려 i번재 글자 까지가 분해할 수 있는지 확인해 가는 방식으로 했다. dp[i]를 특정 위치에서 양쪽으로 나눈다면 왼쪽과 오른쪽이 모두 분해 가능할 때 dp[i] 또한 분해 가능하다고 할 수 있다.
따라서 dp[i]에서의 값을 확인하기 위해서 i 까지의 각 위치 j를 기준으로 하여 왼쪽 구간이 분해 가능한지 기존 dp배열에서 확인한 후 뒷 구간은 사전 내에서 찾아보았다. 글자 수를 늘리면서 dp배열을 확인해 왔기 때문에 0번 인덱스에서 j 번 인덱스까지는 확인되고 저장되어 있기 때문에 빠른 속도로 체크가 가능하다. 아래는 최종적으로 통과한 코드이다.

import java.util.*;  
  
public class Solution {  
  
    public boolean wordBreak(String s, List<String> wordDict) {  
        boolean[] dp = new boolean[s.length() + 1];  
        dp[0] = true;  
  
        for(int i = 0; i < dp.length; i++){  
            for(int j = 0; j <= i; j++){  
                if(dp[j] == true){  
                    String check = s.substring(j, i);  
                    if(wordDict.contains(check)){  
                        dp[i] = true;  
                        break;  
                    }  
                }  
            }  
        }  
  
        return dp[s.length()];  
    }  
  
}

https://leetcode.com/problems/burst-balloons/description/

풍선을 터트리는 순서에 따라 얻는 점수가 다를 때 가장 크게 점수를 얻을 수 있는 방법에 대해 묻는 문제이다. DP 문제로 아이디어를 열심히 생각해 보았지만 잘 떠오르지 않아 해당 문제의 팁을 찾아보고 통과할 수 있었다.

풍선을 터트렸을 때 얻는 점수는 양쪽 좌우 잔여 풍선이 어떤지에 따라 다르다. 이 문제의 점화식의 아이디어는 특정 풍선을 터트릴 때 좌우로 구간이 나뉘며 문제를 작게 볼 수 있다는 점이다.

1 2 3 4 5 의 풍선이 있을 때 3을 터트릴 경우
1 2 - 3 - 4 5 문제를 3구간으로 나눌 수 있다.
1 2 구간의 최대 가능 점수, 3을 터트렸을 때의 점수, 4 5 구간의 최대 가능 점수이다.

이러한 사실을 이용해서 점화식을 세우고, 큰 구간의 점수를 계산하기 위해서 작은 구간의 최대 점수부터 차례대로 큰 구간의 점수를 찾아가는 형태의 순회를 해야 한다. 또한 주어진 조건에 따라 기본 풍선 점수 표 양 끝에 1점의 임의 점수를 추가해주면 문제를 코드를 작성하기에 편의성이 생긴다. 이러한 점들을 고려하며 통과한 최종 코드는 아래와 같다.

public class Solution {  
    public int maxCoins(int[] nums) {  
        int[] arr = new int[nums.length + 2];  
        for(int i = 0; i < nums.length; i++){  
            arr[i + 1] = nums[i];  
        }  
        arr[0] = 1;  
        arr[arr.length - 1] = 1;  
        int n = arr.length;  
  
        int[][] dp = new int[n][n];  
  
        for(int k = 0; k < n - 2; k++){  
            for(int l = 1; l + k <= n - 2; l++){  
                int r = l + k ;  
                for(int j = l; j <= r; j++){  
                    int front = dp[l][j - 1];  
                    int shoot =  arr[l - 1] * arr[j] * arr[r + 1];  
                    int back = dp[j + 1][r];  
  
                    dp[l][r] = Math.max(dp[l][r], front + shoot + back);  
                }  
            }  
        }  
  
        return dp[1][n - 2];  
    }  
  
}

https://leetcode.com/problems/edit-distance/

이번 문제는 DP 문제로 1번 문자열을 2번 문자열로 변환 시킬 때 삽입,삭제,대체 의 세가지 기능을 이용하여 최소 몇 번으로 변화 시킬 수 있는지 묻는 문제이다. DP 문제라는 것을 알고도 아이디어가 떠오르지 않아 한참 고민하다 결국 정답 영상을 찾아 보고야 말았다. 정답을 확인하고 나니 이전에 풀었던 최대 부분 문자열 찾기 문제랑 흡사한 형태였다. 해당 문제는 아래에 있다.

https://leetcode.com/problems/longest-common-subsequence/

이 문제를 풀이 이해하기 위해선 DP 배열 표를 만들어 보면 이해하기 쉽다. 문제에 주어진 예제중 하나인 horse 와 ros 를 기준으로 예외 표를 아래와 같이 그릴 수 있다.

각 좌표에서의 값을 분석해보자 우선 1행과 1열의 값을 보자.
빈 문자열에서 h, ho, hor, hors, hosrse 의 문자열을 만들기 위해선 삽입이란 행동이 필요하므로 1씩 증가한다. 마찬가지의 원리로 1열 또한 증가한다. 임의의 행, 열에서 각각의 행 문자와 열 문자가 같다면 i - 1, j - 1의 값과 같다. 예를 들어 hors 와 ros 의 최소 변환 값은 hor과 ro의 변환 값과 같다. 마지막 s는 변환이 필요 없기 때문이다. 따라서 i - 1, j - 1인 hor, ro의 값과 같다는 점을 알 수 있다.

한편 행과 열의 추가 문자가 다른 경우를 보자 ho와 r의 경우 2이다. 이 경우는 h, r 에서 o를 삭제하는 행위가 추가되는 경우이고, , h,""의 경우의 수에 o를 r로 대체하는 경우의 수가 추가되는 경우이다. 이처럼 i - 1의 경우 삽입의 경우의 수가 늘어나고, j - 1 의 경우 삭제의 경우의 수가 늘어나는 경우, 그리고 i - 1, j - 1 의 경우 대체의 경우의 수가 늘어나는 경우이다.

특정 i, j 에서 글자 수가 생성된다면 이 경우의 수에 한 번의 삽입, 삭제, 대체로 변환 시킬 수 있다. 따라서 최소 변환 방법은 (i, i - 1), (j, j - 1), (i - 1, j - 1)의 값 중에서 가장 작은 값에 1을 추가 시킨 경우이다. 이를 이용하여 점화 식을 만들어 해결하면 아래와 같은 코드가 나온다.

 public class Solution {  
    public int minDistance(String word1, String word2) {  
        int m = word1.length() + 1;  
        int n = word2.length() + 1;  
  
        int[][] dp = new int[m][n];  
  
        for(int i = 0; i < m; i++){  
            dp[i][0] = i;  
        }  
  
        for(int j = 0; j < n; j++){  
            dp[0][j] = j;  
        }  
  
        for(int i = 1; i < m; i++){  
            char c1 = word1.charAt(i - 1);  
            for(int j = 1; j < n; j++){  
                char c2 = word2.charAt(j - 1);  
                if(c1 == c2){  
                    dp[i][j] = dp[i - 1][j - 1];  
                }else{  
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1;  
                }  
            }  
        }  
  
        return dp[m - 1][n - 1];  
    }  
}

https://leetcode.com/problems/coin-change/description/

주어진 코인 종류로 목표 금액을 맞추기 위해 필요한 최소 개수를 구하는 문제이다. dp 문제로 어떻게 풀어낼지 고민하다가 에라토스테네스의 체 알고리즘이 떠올랐다. 해당 알고리즘은 소수를 구하는 알고리즘으로 소수들로 이루어질 수 있는 약수들을 하나씩 체에 거르는 식으로 지워가는 방법이다.

그와 마찬가지로 이 문제의 경우 코인의 종류 별로 이룰 수 있는 값들의 최소 개수를 dp 배열에 적어가며 업데이트 하며 문제를 해결해 나갔다. 작은 값부터 하여 dp[0]은 0인 값으로 코인 1개일 때의 값을 적절히 계산될 수 있도록 초기화 해준 이후 조건에서 제시한 최대 값을 기준으로 극한 값을 설정해주었다. 아래는 최종 코드이다.

import java.util.Arrays;  
  
public class Solution {  
    public int coinChange(int[] coins, int amount) {  
        Arrays.sort(coins);  
  
        int[] dp = new int[amount + 1];  
        int INF = 10001;  
        Arrays.fill(dp, INF);  
        dp[0] = 0;  
  
        for (int i = 0; i < coins.length; i++) {  
            int coin = coins[i];  
            for (int j = coin; j <= amount; j++) {  
                dp[j] = Math.min(dp[j - coin] + 1, dp[j]);  
            }  
        }  
  
  
        return dp[amount] == INF ? -1 : dp[amount];  
    }  
}

https://leetcode.com/problems/house-robber/description/

주어진 배열의 값이 집의 돈이라고 할 때, 연속된 집을 훔칠 수 없다면 최선으로 훔쳤을 때의 최대 돈의 값을 계산하는 문제이다. DP 문제로 해결할 수 있으며 점화식을 세워야 한다.

연속되지 않는 것이 중요하기 때문에 특정 위치 n 에서 최대로 훔칠 수 있는 돈은

1. n - 1일까지 최대로 훔치고 n일차에 훔치지 않은 경우
2. n - 2 일차에 훔치고 n - 1 일차에 훔치지 않은 후에 n 일차에 훔치는 경우이다

n - 2 일차를 기준으로 해야 하기에 1일차, 2일차의 경우 조건이 바뀐다.

1. 1일차의 경우 바로 그날을 훔치는 경우
2. 2일차의 경우 1일차에 훔치거나 2일차에 훔치거나이다

문제 조건에서 n = 1부터 가능하므로 이를 if문으로 예외 처리해주고 점화식을 세웠다. 최종적으로 배열의 마지막 값(마지막 날)을 리턴해주면 된다.

public class Solution {  
    public int rob(int[] nums) {  
  
        int[] dp = new int[nums.length];  
        dp[0] = nums[0];  
        if(nums.length == 1) return dp[0];  
  
        dp[1] = Math.max(nums[1], dp[0]);  
        if(nums.length == 2) return dp[1];  
  
        for(int i = 2; i < nums.length; i++){  
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);  
        }  
  
        return dp[nums.length - 1];  
    }  
}

https://leetcode.com/problems/climbing-stairs/description/

계단을 1, 2 단씩 오를수 있을때 n계의 계단을 오르는 방법의 개수를 묻는 DP 문제이다.
n번재 계단을 오르기 위해선 n-1 번째에서 한 걸음, n-2 에서 두 걸음 오르는 방법이 있으므로

해당 방식으로 dp 점화식을 만들어 문제를 해결하였다.

public class Solution {  
    public int climbStairs(int n) {  
        int[] dp = new int[46];  
        dp[0] = 0;  
        dp[1] = 1;  
        dp[2] = 2;  
  
        for(int i = 3; i <= n; i++){  
            dp[i] = dp[i - 2] + dp[i - 1];  
        }  
  
        return dp[n];  
    }  
}