[알고리즘] 동적 계획법(Dynamic Programming, DP)

1. 동적 계획법(Dynamic Programming)이란?

동적 계획법은 큰 문제를 작은 문제로 나누어 푸는 분할 정복(Divide and Conquer) 기법의 일종으로, 부분 문제의 결과를 재사용하여 중복 계산을 줄이는 알고리즘 설계 기법이다.

---

2. 동적 계획법의 특징

1. 최적 부분 구조(Optimal Substructure)

• 큰 문제의 최적해가 작은 부분 문제의 최적해로 구성된다.

 

2. 중복되는 부분 문제(Overlapping Subproblems)

• 동일한 작은 문제를 여러 번 반복하여 풀게 되는 성질이 있다.
• 이 중복 계산을 줄이기 위해 결과를 저장한다.

---

3.  동적 계획법의 장단점

장점

• 중복 계산을 제거하여 효율성을 극대화
• 재귀적 접근보다 명확하고 빠른 해결 가능

단점

• 상태 저장을 위한 추가 메모리 공간 필요
• 문제에 최적 부분 구조가 없으면 적용 불가

---

4. 동적 계획법의 접근 방법

1. 상향식 접근(Bottom-Up)

•  작은 문제부터 해결해 결과를 저장하고, 이를 기반으로 큰 문제를 해결
• 일반적으로 테이블(Tabluation) 방식으로 구현

 

2. 하향식 접근(Top-Down)

•  큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출하며 결과를 저장
• 일반적으로 메모이제이션(Memoization) 방식으로 구현

---

5. 동적 계획법의 시간 복잡도

• 동적 계획법의 시간 복잡도는 문제의 부분 문제 수와 각 부분 문제를 푸는 데 걸리는 시간의 곱으로 계산된다.
• 예: 피보나치 수열의 DP 구현 -> O(n)

---

6. 동적 계획법의 활용 예시

1. 최적 경로 찾기

• 예: 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford)

2. 배낭 문제(Knapsack Problem)

• 제한된 무게 내에서 최대 가치를 찾는 문제

3. 최장 공통 부분 수열(LCS, Longest Common Subsequence)

• 두 문자열의 간의 최장 공통 부분을 찾는 문제

4. 동전 거스름돈 문제

• 최소 동전 개수로 거스름돈을 만드는 방법 찾기

---

7. 동적 계획법의 구현 예제

예제 1: 피보나치 수열

1. 재귀 방식 (비효율적)

public class FibonacciRecursive {
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10)); // 출력: 55
    }
}

 

2. 메모이제이션 방식 (Top-Down)

import java.util.*;

public class FibonacciMemoization {
    private static Map<Integer, Integer> memo = new HashMap<>();

    public static int fibonacci(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);

        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10)); // 출력: 55
    }
}

 

 

3. 테이블 방식 (Bottom-Up)

 

public class FibonacciTabulation {
    public static int fibonacci(int n) {
        if (n <= 1) return n;

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10)); // 출력: 55
    }
}

---

동적 계획법은 복잡한 문제를 효율적으로 해결할 수 있는 강력한 도구이다.

특히 코딩 테스트에서 빈번히 등장하므로, 재귀와 반복을 활용한 구현 방식 모두 숙달해 두는 것이 중요하다.