꿀잠

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/longest-increasing-subsequence/

배열 내에 값이 증가하는 최대 길이를 찾는 문제이다. 현재 값 보다 이전의 작은 값들일 때의 길이 값을 알면 1을 더하여 현재 최대 가능 길이 값을 구할 수 있다. 이전에 현재 값보다 작은 값이 없다면 1이 된다.

DP 배열을 만들어 배열에 길이 값을 저장하여 문제를 풀어주었다. 아래의 코드와 같이 다이나믹 프로그래밍 방식으로 풀어 통과하였다.

public class Solution {  
    public int lengthOfLIS(int[] nums) {  
        int[] dp = new int[nums.length];  
        dp[0] = 1;  
  
        int answer = 1;  
        for(int i = 1; i < nums.length; i++){  
            int num = nums[i];  
            int search = i;  
            dp[i] = 1;  
            while(search-- > 0){  
                int compare = nums[search];  
                if(compare < num){  
                    dp[i] = Math.max(dp[search] + 1, dp[i]);  
                }  
            }  
  
            answer = Math.max(dp[i], answer);  
        }  
  
        return answer;  
    }  
}

문제 풀이 후 다른 해답 중에 이진 탐색을 쓰는 경우도 있었다. 숫자 배열을 만들고 정렬하며 현재의 num 값을 삽입해주는 형태였다. 삽입 해주어야 하는 인덱스를 이진 탐색을 이용할 경우 DP로 풀때 O2 의 시간복잡도를 갖지만, 이진탐색의 경우 O(n log(n)) 의 시간복잡도로 더욱 빠르게 해결되는 것으로 확인하였다. 아래와 같이 java의 이진 탐색 메서드를 통해 쉽고 더 빠른 구현이 가능하다.

public class Solution {
    public int lengthOfLIS(int[] nums) {            
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = Arrays.binarySearch(dp, 0, len, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
}

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];  
    }  
}