동적 계획법 핵심 개념

동적 계획법은 중복 하위 문제가 많은 최적화 문제에 효과적입니다. 문제를 하위 문제로 분해하고, 동일 계산을 반복하지 않도록 결과를 저장합니다. 최적 부분 구조가 존재해야 적용 가능하며, 이는 지역 최적해가 전역 최적해로 이어지는 구조를 의미합니다. 핵심은 상위 문제 해결에 하위 문제의 결과가 재사용되는 점입니다.

대표적인 예로 피보나치 수열이 있으며, 다음 세 단계로 해결합니다:

1. 일반화된 점화식 도출
2. 초기 경계값 설정
3. 반복 계산 수행

문제 해결 사례

계단 오르기 (LeetCode 70)

n계단을 1/2칸씩 오를 때 가능한 방법의 수를 구합니다. 점화식:

public int countStairPaths(int steps) {
    int[] result = new int[steps + 2];
    result[0] = 1;
    result[1] = 1;
    
    for (int i = 2; i <= steps; i++) {
        result[i] = result[i - 1] + result[i - 2];
    }
    return result[steps];
}

가방 훔치기 (LeetCode 198)

인접하지 않은 집들에서 최대 금액을 훔치는 문제입니다. 점화식:

public int robHouses(int[] amounts) {
    if (amounts.length == 0) return 0;
    if (amounts.length == 1) return amounts[0];
    
    int[] maxValue = new int[amounts.length];
    maxValue[0] = amounts[0];
    maxValue[1] = Math.max(amounts[0], amounts[1]);
    
    for (int i = 2; i < amounts.length; i++) {
        maxValue[i] = Math.max(maxValue[i - 1], maxValue[i - 2] + amounts[i]);
    }
    return maxValue[amounts.length - 1];
}

동등 부분집합 분할 (LeetCode 416)

배열을 합이 같은 두 부분집합으로 분할 가능 여부 판단합니다.

2차원 접근

public boolean canSplitArray(int[] numbers) {
    int total = Arrays.stream(numbers).sum();
    if (total % 2 != 0) return false;
    int half = total / 2;
    boolean[][] dp = new boolean[numbers.length][half + 1];
    dp[0][0] = true;
    
    for (int i = 1; i < numbers.length; i++) {
        for (int j = 0; j <= half; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= numbers[i]) {
                dp[i][j] |= dp[i - 1][j - numbers[i]];
            }
        }
    }
    return dp[numbers.length - 1][half];
}

1차원 최적화

public boolean canSplitOptimized(int[] numbers) {
    int total = Arrays.stream(numbers).sum();
    if (total % 2 != 0) return false;
    int half = total / 2;
    boolean[] dp = new boolean[half + 1];
    dp[0] = true;
    
    for (int num : numbers) {
        for (int j = half; j >= num; j--) {
            dp[j] |= dp[j - num];
        }
    }
    return dp[half];
}

영상 클립 병합 (LeetCode 1024)

[0,T] 구간을 커버하는 최소 클립 수를 구합니다.

public int minClips(int[][] clips, int T) {
    int[] dp = new int[T + 1];
    Arrays.fill(dp, Integer.MAX_VALUE - 1);
    dp[0] = 0;
    
    for (int t = 1; t <= T; t++) {
        for (int[] clip : clips) {
            if (clip[0] < t && t <= clip[1]) {
                dp[t] = Math.min(dp[t], dp[clip[0]] + 1);
            }
        }
    }
    return dp[T] == Integer.MAX_VALUE - 1 ? -1 : dp[T];
}

단어 분할 II (LeetCode 140)

문자열을 사전 단어로 분할하는 모든 경우를 생성합니다.

public List<String> wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    boolean[] valid = new boolean[s.length() + 1];
    valid[0] = true;
    
    for (int end = 1; end <= s.length(); end++) {
        for (int start = 0; start < end; start++) {
            if (valid[start] && dict.contains(s.substring(start, end))) {
                valid[end] = true;
                break;
            }
        }
    }
    
    List<String> results = new ArrayList<>();
    if (valid[s.length()]) {
        dfs(s, s.length(), dict, valid, new ArrayDeque<>(), results);
    }
    return results;
}

private void dfs(String s, int end, Set<String> dict, boolean[] valid, 
                 Deque<String> path, List<String> results) {
    if (end == 0) {
        results.add(String.join(" ", path));
        return;
    }
    for (int start = end - 1; start >= 0; start--) {
        String word = s.substring(start, end);
        if (dict.contains(word) && valid[start]) {
            path.push(word);
            dfs(s, start, dict, valid, path, results);
            path.pop();
        }
    }
}