DP

Dynamic Programming (동적 계획법)

복잡한 문제를 더 작은 하위 문제로 나누어 해결하고, 각 하위 문제의 결과를 저장하여 재사용함으로써 계산 효율성을 높이는 알고리즘 설계 기법입니다. 이를 통해 중복 계산을 피하고 최적해를 찾을 수 있습니다.

핵심 요소

핵심요소	설명
최적 부분 구조	큰 문제의 최적해가 작은 문제의 최적해를 포함
중복되는 부분 문제	동일한 작은 문제들이 반복적으로 나타남
메모이제이션	계산 결과를 저장하여 재활용
테이블링	반복적 방식으로 문제를 해결하며 결과 저장

DP 해결 과정

graph TD;
A["문제 분석"] --> B["부분 문제 식별"];
B --> C["점화식 수립"];
C --> D["메모이제이션/테이블링 구현"];
D --> E["베이스 케이스 처리"];
E --> F["최종 해답 도출"];
Mermaid
복사

예시 코드 - 피보나치 수열

public class Fibonacci {
    public static int fib(int n) {
        // 메모이제이션을 위한 배열
        int[] dp = new int[n + 1];
        
        // 베이스 케이스
        dp[1] = 1;
        dp[2] = 1;
        
        // 상향식 접근
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        
        return dp[n];
    }
    
    public static void main(String[] args) {
        System.out.println(fib(10)); // 55 출력
    }
}
Java
복사

이 코드는 피보나치 수열을 DP를 사용하여 구현한 예시입니다. 재귀적 방식 대신 반복문과 배열을 사용하여 효율적으로 계산합니다.

대표적인 DP 문제

•

피보나치 수열: 이전 두 수의 합으로 현재 수를 구하는 문제

•

최단 경로 문제: 그래프에서 두 정점 사이의 최단 거리를 찾는 문제

•

배낭 문제: 제한된 무게 내에서 최대 가치를 얻는 물건 조합을 찾는 문제

메모이제이션 (Memoization)

메모이제이션은 동적 계획법에서 사용되는 최적화 기법으로, 이미 계산한 결과를 메모리에 저장하여 동일한 계산의 반복 수행을 방지하는 방법입니다.

메모이제이션의 주요 특징:

•

하향식 접근(Top-down): 큰 문제에서 작은 문제로 분할하며 해결

•

재귀적 구현: 주로 재귀 함수와 함께 사용되어 자연스러운 문제 해결 과정을 표현

•

캐시 활용: 배열이나 해시맵을 사용하여 계산 결과를 저장하고 재사용

public class FibonacciMemo {
    private static Map<Integer, Long> memo = new HashMap<>();
    
    public static long fib(int n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        if (n <= 2) {
            return 1;
        }
        memo.put(n, fib(n-1) + fib(n-2));
        return memo.get(n);
    }
}
Java
복사

테이블링 (Tabulation)

테이블링은 동적 계획법의 반복적 방식으로, 작은 부분 문제부터 차례대로 해결하며 테이블(배열)에 결과를 저장하는 방법입니다.

테이블링의 주요 특징:

•

상향식 접근(Bottom-up): 가장 작은 부분 문제부터 시작하여 큰 문제를 해결

•

반복문 사용: 일반적으로 for 루프를 사용하여 구현

•

공간 효율성: 필요한 결과만 저장하여 메모리 사용을 최적화 가능

public class FibonacciTable {
    public static long fib(int n) {
        if (n <= 2) return 1;
        
        long[] dp = new long[n + 1];
        dp[1] = dp[2] = 1;
        
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
Java
복사