DP의 개념과 특징

dp란?

문제를 작은 부분 문제들로 나누어 해결하고, 그 해답을 재활용하여 전체 문제를 해결하는 알고리즘.

중복되는 부분문제, 최적 부분 구조 문제에 적용된다. 메모이제이션과 타뷸레이션 방식을 통해 시간 복잡도를 크게 줄일수 있다.

 

dp를 구성하는 핵심 개념

1. 메모이제이션 (Memoization)
   • 주로 재귀 호출과 함께 사용
   • 필요한 부분 문제를 만나면 그때 계산하며, 계산된 결과는 캐시에 저장함.
   • 탑다운(Top-down) 방식이라고 부름. 
   • 메모리 사용량이 더 많을 수 있지만, 불필요한 부분은 계산하지 않기 때문에 효율적임
   • 각 부분 문제는 최대 한 번만 계산됨.
2. 타뷸레이션 (Tabulation)
   • 주로 반복문을 사용하여, 작은 문제부터 순차적으로 해답을 구해가는 방식
   • 모든 부분 문제를 미리 계산해 테이블에 저장함.
   • 바텀업(Bottom-up) 방식이라고도 부름.
   • 모든 작은 문제를 순차적으로 계산하기 때문에 불필요한 문제도 계산 될수 있음.
   • 보통 메모리 사용량이 더 효율적일 수 있음.

※ 메모이제이션은 해시 테이블이나 배열 같은 테이터 구조를 사용하고 재귀적으로 호출된 함수들이 스택 메모리에 쌓이기 때문에, 재귀가 깊어질수록 스택에 많은 함수 호출이 쌓이므로, 재귀 호출 깊이에 따라 추가적인 메모리가 필요하다. 따라서 재귀가 깊어질수록 스택 오버플로우 위험이 커진다.

※ 타뷸레이션은 재귀 호출을 사용하지 않기 때문에, 반복문만으로 문제를 해결하므로 추가적인 스택 메모리가 필요하지 않다. 미리 정의된 테이블(배열) 크기만큼의 메모리만 사용한다. 따라서 메모리 오버헤드가 적다.

 

 

dp 알고리즘의 3단계

1. 부분 문제 정의
2. 점화식 설정 
3. 초기값 설정

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] ans = new int[amount+1];
        Arrays.fill(ans, amount+1);
        ans[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(int j = 0; j < coins.length; j++){
                if(i - coins[j] >= 0){
                    ans[i] = Math.min(ans[i], 1 + ans[i-coins[j]]);
                }
            }
        }

        return ans[amount] != amount + 1 ? ans[amount] : -1;
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 문자열을 첨부터 끝까지 돌면서 사전의 단어와 일치하는지 비교한다.
        // 일치할때, 그 전의 문자열도 일치했었는지가 중요하다. 
        // 그래서 이를 저장해서 확인할 수 있는 문자열과 비슷한 길이의 배열이 필요하다. 
        // => dp의 중요 개념 중 하나! 저장!
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        
        // substring 할때 해당 인덱스 전까지 자르므로 1부터 시작!
        for(int i = 1; i <= s.length(); i++){
            for(String word: wordDict){
                // 사전의 단어와 일치하는지 보려면 사전의 단어별로 시작점을 각각 잡아야함! 단어별로 길이가 다르기때문.
                int start = i - word.length();
                // 사전의 단어와 일치하고, 
                // 지금 일치하는 단어 전 문자열도 사전에 있었는지(dp[start]의 값이 true) 확인!
                if(start >= 0 && dp[start] && s.substring(start,i).equals(word)){
                    // 사전에 있었다고 표시
                    dp[i] = true;
                    break;
                }
            }
        }

        // dp[]의 true 체크 조건이, 직전 것들이 모두 사전에 있었다(true)라는 조건이기에
        // 맨 마지막 요소가 그 결과임.
        return dp[s.length()];
    }
}

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;

        if(n == 1){
            return nums[0];
        }

        // i번 집을 털때 or 안털때에 대한 최댓값을 저장
        int[] dp = new int[n];

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        // i번 집을 털때와 안털때 중 큰 값을 dp에 넣기
        // 점화식이 성립하는 이유.. 아래 처럼 두가지로 나누고 최대만 보면 됨
        // => i번 집을 안털 때 : dp[i-1]
        // => i번 집을 털 때 : nums[i] + dp[i-2]
        for(int i = 2; i < n; i++){
            dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2]);
        }

        return dp[n-1];
    }
}

 

• 작은 문제들의 해답을 구해서 저장해두는 배열의 크기를 '주어진 배열의 크기+1'의 크기로 설정하는 것을 볼수있다.
• 왜? 문제에서 목적지점이 따로 정해지지 않은 경우, 마지막 요소가 주어진 전체 배열의 해답을 합한 최종값이므로..

 

dp로 풀어야하는 문제의 특징

1. 인접하거나 상호 의존하는 부분이 있을때 
2. 구간이나 특정조건에 따라 최적해를 계산해야할 때 
3. 재귀적 관계로 문제를 풀수 있을때, 어떤상태가 이전상태에 의존하는 경우 (피보나치 수열)

 

dp가 적합한 경우

• 최댓값, 최솟값을 구하는 경로 탐색 문제로, 각 상태가 이전 상태의 최적해에 의존하는 경우
• 배열이나 이차원 배열을 탐색하면서 부분 문제의 중복이 존재하고, 최적 부분구조를 만족하는 경우
• ex) House Robber, 최대부분합, 최소비용경로, 경로가 존재하는지 여부 등.

dp가 적합하지 않은 경우 (그래프가 적합한 경우)

• 최단 이동 거리를 구하는 문제로, BFS나 Dijkstra가 효율적인 경우
• 가중치가 같은 경로 탐색 : BFS
• 가중치가 다양한 경로 탐색 : Dijkstra
• 가중치가 음수인 경로 탐색 : Bellman-Ford (음수 사이클이 있는지도 확인 가능)
• ex) 최단 경로 탐색 문제, 장애물이 있는 그리드에서 최소 이동 거리 구하기 등

※ 그리드도 그래프의 일종이다. 그리드는 각 셀이 고정된 위치를 가진다. 그래프는 노드와 간선으로 이루어진 비정형적인 구조로, 각 노드는 자유롭게 다른 노드와 연결될 수 있고, 연결은 방향성이나 가중치가 있을 수 있다.

 

 

 

※ 관련문제

https://gimmesome.tistory.com/260

Leet code (Medium) : 322. Coin Change - JAVA

 

https://gimmesome.tistory.com/261

Leet code (Medium) : 139. Word Break - JAVA

 

https://gimmesome.tistory.com/262

Leet code (Medium) : 377. Combination Sum IV - JAVA

 

https://gimmesome.tistory.com/263

Leet code (Medium) : 198. House Robber - JAVA

 

https://gimmesome.tistory.com/264

Leet code (Medium) : 55. Jump Game - JAVA