동적 프로그래밍 (Dynamic Programming)

출처 : https://velog.io/@cyranocoding/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohia5

 

최적화 문제를 해결하기 위한 알고리즘 패러다임 중 하나로, 하위 문제의 해결 결과를 저장하고 활용하여 중복 계산을 피하는 방법

 

• 탑다운(DP with Memoization)
  재귀적인 방식으로 문제를 해결하면서 중복 계산을 피하기 위해 이전에 계산한 결과를 메모리에 저장
  재귀 함수와 메모이제이션(캐싱)
  
  
• 바텀업(Bottom-Up DP)
  작은 부분 문제부터 시작하여 전체 문제의 해결 방법을 구하는 방식
  반복문을 사용하며, 주로 반복적 동적 프로그래밍 또는 테이블을 활용
  
  
• 0/1 배낭 문제(Knapsack Problem)
  일정한 용량을 가진 배낭에 가치와 무게가 다른 물건들을 넣을 때 최대 가치를 얻는 문제
  무게 제한이 있는 배낭 문제와 무게 제한이 없는 배낭 문제로 나뉨
  
  
• 최장 증가 부분 수열(LIS - Longest Increasing Subsequence)
  주어진 수열에서 순서를 유지하면서 가장 긴 부분 수열을 찾는 문제
  주로 탑다운 방식으로 해결
  
  
• 피보나치 수열(Fibonacci Sequence)
  n번째 피보나치 수를 구하는 문제로, 재귀적인 방식에서 중복 계산을 피하는데 사용
  재귀적방법, 탑다운 방식 또는 바텀업 방식으로 해결
  
  

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

    public static void main(String[] args) {
        int n = 10; // 계산할 피보나치 수열의 항
        int result = fibonacci(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}

import java.util.Arrays;

public class FibonacciTopDownTest {
    static long[] memo; // 계산 결과를 저장할 배열

    public static long fibonacci(int n) {
        // 이미 계산한 값이 있다면 그 값을 반환
        if (memo[n] != -1) {
            return memo[n];
        }

        // 피보나치 수열의 정의에 따라 값을 계산
        if (n <= 1) {
            memo[n] = n;
        } else {
            memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
        }

        return memo[n];
    }

    public static void main(String[] args) {
        int n = 10; // 계산할 피보나치 수열의 항
        memo = new long[n + 1];
        // memo 배열을 -1로 초기화
        Arrays.fill(memo, -1);

        long result = fibonacci(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}

public class FibonacciBottomUpTest {
    public static long fibonacci(int n) {
        if (n <= 1) {
            return n;
        }

        long[] dp = new long[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) {
        int n = 10; // 계산할 피보나치 수열의 항
        long result = fibonacci(n);
        System.out.println("Fibonacci(" + n + ") = " + result);
    }
}

• 그래프 알고리즘 (Dynamic Programming on Graphs)
  그래프 문제에서 동적 프로그래밍을 활용하여 최단 경로, 최소 신장 트리 등을 구하는데 사용
  다익스트라 알고리즘, 벨만-포드 알고리즘
  
  
• 분할 정복과 동적 프로그래밍 (Divide and Conquer with DP)
  분할 정복 기법과 동적 프로그래밍을 조합하여 문제를 해결하는 방식
  복잡한 문제를 더 작은 부분 문제로 분할하고, 그 부분 문제들을 동적 프로그래밍으로 해결