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

다다면체 2024. 12. 24. 09:00

728x90

안녕하세요! 🙌 오늘은 프로그래머라면 한 번쯤은 마주칠 **동적 계획법(Dynamic Programming, DP)**을 재밌고 쉽게 풀어보려고 해요! 🎉 하나씩 단계별로 알아보며 "어? 생각보다 쉽네!" 라는 감탄사가 나오도록 해볼게요. 🌟

🧩 1. 기본 DP 문제

🎯 피보나치 수열 (Fibonacci Sequence)

DP의 입문은 역시 피보나치죠! 🌀 재귀로 계산하면 시간이 너무 오래 걸리지만, DP를 활용하면 빠르게 계산 가능해요! 💨
피보나치 수열은 재귀로도 계산할 수 있지만, 동일한 계산을 반복하면서 시간 복잡도가 급격히 증가합니다. DP는 이런 중복 계산을 제거하는 핵심 기법입니다.

✏️ 코드

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

📌 핵심 개념

작은 문제의 해를 저장:
dp[i]에 피보나치 수열의 i번째 값을 저장합니다.
중복 계산 방지:
재귀 방식에서는 동일한 값을 여러 번 계산하지만, DP는 한 번 계산한 값을 재사용합니다.
예를 들어, f(4)를 계산하려면 f(3)과 f(2)를 사용하는데, 이미 계산된 값이므로 추가 연산이 없습니다.
시간 복잡도:
- 재귀 방식: 지수 시간 복잡도 O(2^n)
- DP 방식: 선형 시간 복잡도 O(n)

🎯 어떤 의미가 있는가?

**DP의 기본 원리인 "메모이제이션(Memoization)"**의 활용을 이해하는 데 최적의 예제입니다.
이 방식을 확장해 탑다운과 바텀업 접근 방식을 구별할 수 있습니다.

🪜 계단 오르기 문제 (Climbing Stairs)

한 번에 1칸 또는 2칸씩 오를 수 있는 계단을 오르는 방법의 수를 구하는 문제입니다.
이 문제는 피보나치 수열과 동일한 원리를 따르며, DP의 재활용성을 잘 보여주는 예제입니다. 🤔

✏️ 코드

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

📌 핵심 개념

재귀적 관계식:
- 계단을 오르는 방법은 n-1 계단에서 1칸을 오르거나, n-2 계단에서 2칸을 오르는 두 가지 방법의 합입니다.
- 따라서, dp[i] = dp[i - 1] + dp[i - 2].
동일한 패턴의 문제 해결:
이 문제는 본질적으로 피보나치 수열 문제와 유사하며, 동일한 접근법으로 해결할 수 있습니다.
확장성:
- "한 번에 1칸, 2칸, 또는 3칸씩 오를 수 있다면?"과 같은 문제로 확장 가능합니다.
- 재귀 관계식은 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]로 변경됩니다.

🎯 어떤 의미가 있는가?

일반화된 패턴 인식: 다양한 유형의 문제를 같은 방식으로 해결할 수 있는 DP의 유연성을 체험할 수 있습니다.
작은 문제를 결합해 더 큰 문제를 해결하는 문제 분할 기법을 명확히 이해할 수 있습니다.

🎒 배낭 문제 (Knapsack Problem)

DP의 대표적인 응용 문제!
주어진 용량의 배낭에 물건을 담아 가치를 최대화하는 방법을 구하는 문제입니다. 💼

✏️ 코드

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][capacity];
}

📌 핵심 개념

문제의 두 가지 선택:
- 물건을 선택하거나(dp[i - 1][w - weights[i - 1]] + values[i - 1]),
- 선택하지 않거나(dp[i - 1][w]).
2D 배열 사용:
- dp[i][w]는 i번째 물건까지 고려했을 때, 용량 w에서 얻을 수 있는 최대 가치입니다.
시간 복잡도:
- O(n * capacity)로, 물건 수와 용량의 곱에 비례합니다.

🎯 어떤 의미가 있는가?

문제를 선택과 배제의 두 가지 관점에서 재귀적으로 접근하는 방법을 이해할 수 있습니다.
다양한 변형 문제(부분합, 배낭 문제의 fractional 버전 등)로 확장 가능합니다.

🧩 2. 2D DP 문제

🔗 최장 공통 부분 수열 (Longest Common Subsequence)

두 문자열의 공통 부분 수열 중 가장 긴 길이를 찾아보자!

문자 하나씩 비교하며 최적해를 계산하는 방식으로, 문자열 문제의 기본 기법입니다. 🔍

✏️ 코드

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

📌 핵심 개념

2D DP 배열의 의미:
- dp[i][j]는 첫 번째 문자열의 i번째까지와 두 번째 문자열의 j번째까지 비교했을 때의 최장 공통 부분 수열 길이를 저장합니다.
재귀 관계식:
- 두 문자가 같다면: dp[i][j] = dp[i - 1][j - 1] + 1
- 다르다면: dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
시간 복잡도:
- O(m * n)로 두 문자열 길이의 곱에 비례합니다.

🎯 어떤 의미가 있는가?

문자열 문제에서 자주 등장하는 기초 알고리즘으로, 패턴 일치 문제로 확장 가능합니다.
2D DP 배열의 구조와 이를 순회하는 방법을 깊이 이해할 수 있습니다.

✍️ 편집 거리 (Edit Distance)

두 문자열 word1과 word2를 변환하기 위해 필요한 삽입(Insertion), 삭제(Deletion), 교체(Replacement) 연산의 최소 횟수를 구하는 문제입니다! 🛠️

✏️ 코드

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

📌 핵심 개념

DP 배열 정의:
- dp[i][j]: word1의 처음 i문자와 word2의 처음 j문자를 일치시키는 데 필요한 최소 연산 횟수.
점화식:
- 문자들이 같을 경우(word1[i - 1] == word2[j - 1]): dp[i][j]=dp[i−1][j−1]dp[i][j] = dp[i-1][j-1]
- 문자들이 다를 경우(word1[i - 1] != word2[j - 1]): dp[i][j]=1+min⁡(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])dp[i][j] = 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
  - dp[i-1][j]: 삭제
  - dp[i][j-1]: 삽입
  - dp[i-1][j-1]: 교체
경계 조건:
- dp[0][j] = j: word1이 빈 문자열인 경우.
- dp[i][0] = i: word2가 빈 문자열인 경우.

🧩 3. 고급 DP 문제

🎭 상태 압축 DP

🔑 예제: 0/1 배낭 문제
기존 2D DP를 사용하면 dp[i][w]처럼 아이템과 무게를 이차원 배열로 저장해야 하지만, 상태 압축을 사용하면 1D 배열로 최적화할 수 있습니다.

✏️ 코드

public int knapsackOptimized(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    
    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}

📌 핵심 포인트

1D 배열 정의:
- dp[w]: 현재 용량 w에서 얻을 수 있는 최대 가치.
뒤에서 앞으로 순회:
- 무게를 줄여가며 갱신하여 이전 상태를 덮어쓰지 않도록 처리.

⚡ 작동 원리

2D 배열에서 dp[i][w]는 i-1번째 상태에 의존합니다.
이를 1D로 축소할 경우, 배열을 역방향으로 업데이트해 이전 상태를 보존합니다.

⛓️ 분할 정복 DP

🔑 예제: 행렬 곱셈 순서 최적화 (Matrix Chain Multiplication)
여러 행렬을 곱할 때 필요한 최소 연산 횟수를 구합니다.

✏️ 코드

public int matrixChainOrder(int[] dims) {
    int n = dims.length - 1;
    int[][] dp = new int[n][n];

    for (int len = 2; len <= n; len++) { // 길이 2부터 시작
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;

            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}

📌 핵심 포인트

문제 구조 분석:
- 행렬 곱셈은 결합 법칙이 성립하지만 순서에 따라 계산 비용이 달라집니다.
- 예: A10×20,B20×30,C30×40A_{10 \times 20}, B_{20 \times 30}, C_{30 \times 40}: (A⋅B)⋅C=(10⋅20⋅30)+(10⋅30⋅40)=18000(A \cdot B) \cdot C = (10 \cdot 20 \cdot 30) + (10 \cdot 30 \cdot 40) = 18000 A⋅(B⋅C)=(20⋅30⋅40)+(10⋅20⋅40)=32000A \cdot (B \cdot C) = (20 \cdot 30 \cdot 40) + (10 \cdot 20 \cdot 40) = 32000 첫 번째 방법이 더 효율적입니다.
DP 배열 정의:
- dp[i][j]: i번째 행렬부터 j번째 행렬까지 곱셈을 수행할 때의 최소 비용.
점화식:
dp[i][j] = \min_{i \leq k < j} (dp[i][k] + dp[k+1][j] + \text{비용}) ]
시간 복잡도:
- O(n3)O(n^3) (3중 반복문).

🎯 추가 예제: 다각형의 최적 삼각 분할

N각형을 삼각형으로 나누어 각 삼각형의 무게 합이 최소가 되도록 분할합니다.

✏️ 코드

public int minScoreTriangulation(int[] values) {
    int n = values.length;
    int[][] dp = new int[n][n];

    for (int len = 2; len < n; len++) { // 최소 길이 3 이상
        for (int i = 0; i < n - len; i++) {
            int j = i + len;
            dp[i][j] = Integer.MAX_VALUE;

            for (int k = i + 1; k < j; k++) {
                int cost = dp[i][k] + dp[k][j] + values[i] * values[k] * values[j];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }

    return dp[0][n - 1];
}

📌 핵심 포인트

DP 배열 정의:
- dp[i][j]: ii번째와 jj번째 꼭짓점을 연결하는 다각형의 최소 비용.
점화식:
- kk를 ii와 jj 사이의 분할점으로 사용: dp[i][j]=min⁡i<k<j(dp[i][k]+dp[k][j]+가중치)dp[i][j] = \min_{i < k < j} (dp[i][k] + dp[k][j] + \text{가중치})
  - 가중치: values[i]⋅values[k]⋅values[j]\text{values}[i] \cdot \text{values}[k] \cdot \text{values}[j].
작동 방식:
- 가능한 모든 kk를 탐색하여 최소 비용을 계산.
시간 복잡도:
- O(n3)O(n^3).

🎉 결론

동적 계획법(DP)은 알고리즘 세상에서 만능 해결사 같은 존재예요! 🤩 작은 문제를 풀어가며 차근차근 큰 문제를 해결하는 과정은 마치 퍼즐을 맞추는 것처럼 짜릿하죠. 🧩

피보나치 수열부터 배낭 문제, 최장 공통 부분 수열까지, 다양한 예제들을 통해 DP의 매력을 흠뻑 느낄 수 있었는데요, 결국 핵심은 **"작은 문제를 잘게 나누고, 중복 계산을 없애는 것"**이에요! DP는 단순히 효율적인 알고리즘을 만드는 걸 넘어, 복잡한 문제를 체계적으로 정리하는 힘을 길러줘요.

또한 고급 기법인 상태 압축이나 분할 정복 DP를 활용하면 "이렇게도 할 수 있구나!"라는 깨달음이 쏟아질 거예요. 한 번 익혀두면 어디서든 써먹을 수 있는 실용적인 도구라 더 매력적이랍니다! 💡

DP는 처음엔 살짝 까다로워 보일 수 있지만, 연습을 거듭하다 보면 점점 친해질 수 있어요. 자신감을 가지고 도전하다 보면, 어느새 "어? 나도 할 수 있네?"라는 뿌듯함이 따라올 거예요. 앞으로도 DP와 함께 문제를 쭉쭉 해결하며, 알고리즘 마스터의 길을 걸어가 보아요! 🚀✨

728x90

저작자표시 비영리 변경금지 (새창열림)