Dynamic Programming의 개념과 종류, 사용 가능 조건과 예제(feat:Optimization Problem)

개요

Dynamic Programming(DP)은 복잡한 문제를 간단한 여러 개의 하위 문제(subproblem)로 나누어 해결하는 알고리즘 설계 기법이다. DP는 각 하위 문제의 해를 저장하여 중복 계산을 피하고, 전체 문제의 최적해를 효율적으로 구하는 데 사용된다. 특히 Optimization Problem을 해결하는 데 매우 효과적이다.

 

내용

Optimization Problem이란?

 Optimization Problem(최적화 문제)은 주어진 조건 하에서 어떤 값을 최소화하거나 최대화하는 문제를 말한다. 예를 들어, 비용을 최소화하거나 이익을 최대화하는 것이 대표적인 최적화 문제이다. 이러한 문제는 하나 이상의 목표를 가지고 있으며, 그 목표를 달성하기 위한 최적의 값을 찾는 것이 주된 목적이다. DP는 Optimization Prolbem을 해결하기 위한 여러가지 알고리즘 중 하나인 것이다.

 

 

DP의 두 가지 구현 방식

 Dynamic Programming에는 크게 두 가지 접근 방식이 있다. Top-Down 방식과 Bottom-Up 방식이 그것이다.

 

• Top-Down 방식
  • 구조: 재귀적(recursive)이다.
  • Subproblem 저장 방식: 메모제이션(memoization)을 사용한다.
  • 선호되는 경우: 일부 하위 문제만 계산해도 최종 최적해를 구할 수 있을 때 적합하다.
• Bottom-Up 방식 (주로 사용됨)
  • 구조: iterative 하다.
  • Subproblem 저장 방식: 테이블화(tabulation)를 사용한다.
  • 선호되는 경우: 모든 하위 문제를 계산해야 최종 최적해를 구할 수 있을 때 적합하다.

 

DP를 사용한 알고리즘 설계 순서

• DP를 활용하여 알고리즘을 설계할 때는 다음과 같은 단계를 거친다
  • 문제의 최적해의 구조 분석: 주어진 문제의 최적 해가 어떻게 구성되는지 파악한다.
  • 재귀적 정의: 최적 해의 값을 재귀적인 형태로 정의한다.
  • Bottom-Up 방식으로 값 계산: 주로 Bottom-Up 방식을 사용하여 최적 해의 값을 계산한다.
  • 결과 도출: 계산된 정보를 바탕으로 최종 최적 해를 도출한다.

 

DP 예제 (Climbing Stairs)

LeetCode의 Climbing Stairs 문제는 DP의 대표적인 예제 중 하나다.

 

문제 설명 문제: 계단이 총 n개 있을 때, 한 번에 1계단 또는 2계단씩 오를 수 있을 때, 계단을 오르는 모든 경우의 수를 구하라.

입력: 정수 n (1 ≤ n ≤ 45)

출력: 계단을 오르는 경우의 수

 

Top-Down 방식 구현 (Java)

import java.util.HashMap;
import java.util.Map;

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

    public int climbStairs(int n) {
        if(n <= 2) return n;
        if(memo.containsKey(n)) return memo.get(n);
        int ways = climbStairs(n-1) + climbStairs(n-2);
        memo.put(n, ways);
        return ways;
    }

    public static void main(String[] args) {
        ClimbingStairsTopDown solution = new ClimbingStairsTopDown();
        int n = 5;
        System.out.println("Number of ways to climb " + n + " stairs (Top-Down): " + solution.climbStairs(n));
    }
}

 

Bottom-Up 방식 구현 (Java)

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

    public static void main(String[] args) {
        ClimbingStairsBottomUp solution = new ClimbingStairsBottomUp();
        int n = 5;
        System.out.println("Number of ways to climb " + n + " stairs (Bottom-Up): " + solution.climbStairs(n));
    }
}

 

DP를 사용할 수 있는 경우(조건)

Dynamic Programming(DP)을 적용할 수 있는 문제는 optimal substructure와 overlapping subproblems라는 두 가지 특성을 만족해야 한다.

 

Optimal Substructure

Optimal Substructure란, 문제의 최적해가 그 문제의 부분 문제들의 최적해로 구성될 수 있다는 성질을 의미한다.

• 즉, 전체 문제의 최적해는 부분 문제들의 최적해들을 조합해서 구할 수 있다는 것이다.
• DP에서는 이 성질을 활용하여, 문제를 작은 부분 문제들로 나누고 그 작은 문제들의 최적해를 구한 후, 이를 이용해 최종 문제의 최적해를 구한다.

 

예시

최단 경로 문제(예: 다익스트라 알고리즘)에서, 한 노드에서 다른 노드로 가는 최단 경로를 구하려면 그 경로에 포함된 다른 노드들의 최단 경로가 필요하다. 즉, 큰 문제를 해결하려면 작은 문제들의 최적해가 필요하고, 이 과정이 반복되면서 전체 문제의 최적해를 구할 수 있다.

 

단, 부분 문제들이 독립적으로 최적해를 구할 수 있어야 하며, 최종 해는 이들 최적해를 조합한 형태여야 한다.

 

Overlapping Subproblems

Overlapping Subproblems란, 문제를 분할하면서 동일한 부분 문제들이 여러 번 계산되는 성질을 의미한다. 즉, 문제를 재귀적으로 해결할 때, 동일한 부분 문제를 여러 번 반복해서 풀게 되는 상황이다. DP에서는 이 중복된 계산을 피하기 위해 메모이제이션(Memoization) 또는 테이블화(Tabulation) 기법을 사용하여, 이미 구한 값을 저장하고, 필요할 때 다시 사용한다.

 

예시

피보나치 수열 문제에서, fib(5)를 구할 때 fib(4)와 fib(3)를 다시 계산하게 된다. 이처럼 같은 계산이 여러 번 일어나므로, 계산된 값을 저장해두고 재사용하는 방식으로 효율적으로 해결할 수 있다.

 

단 동일한 부분 문제들이 여러 번 등장하므로, 이전에 계산한 값을 재사용할 수 있어야 한다.

 

참고 자료