알고리즘 - 동적 계획법(Dynamic Programming)

 

 

 

 

 

 

 

 

동적 계획법이란 ?

 

 

• 동적 계획법은 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어져 있을때, 각 단계의 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법이다.
• 복잡한 하나의 문제를 간단한 하위 문제들로 나눠서 푸는 최적화 기법이다.
• 동적 계획법을 사용하려면 문제의 유형이 최적 부분 구조(Optimal Substructure) 이거나,
  중복되는 부분 문제(Overlapping Subproblems) 로 이루어 져야 한다.

 

 

동적 계획법과 분할 정복의 차이점

 

 

• 동적 계획법과 분할 정복은 큰 문제를 작은 여러 문제로 나눈다는 점에서는 비슷하다.
• 하지만 문제 접근 방식이나 사용되는 문제의 유형에 있어서는 확연한 차이를 보여준다.

 

요소	동적 계획법(DP)	분할 정복(Divide and Conquer)
하위 문제 중복 여부	하위 문제가 중복된다.	하위 문제가 중복되지 않는다.
문제 해결 방식	결과를 저장하여 재사용한다. (Memoization / Tabulation)	하위 문제를 독립적으로 해결 후 합친다
계산 최적화 방식	저장된 결과를 재사용하여 최적화한다.	하위 문제를 독립적으로 해결한다 (재귀)
대표적인 알고리즘	피보나치 수열, 최장 공통 부분 수열(LCS) 등	Quick Sort, 이진 검색, Merge Sort 등
사용 예시	중복되는 하위 문제가 많은 최적화 문제	문제를 독립적으로 하위 문제로 나눌 수 있는 문제

 

 

 

 

동적 계획법의 구현 방식

 

 

• 탑 다운(Top-down) 방식

     -   재귀적 방법을 사용하여 큰 문제를 작은 문제로 나누어 해결한다.
     -   *메모이제이션 을 사용하여 계산 결과를 저장해 동일한 계산을 반복하지 않도록 한다.

 

 

• 바텀 업(Bottom-up) 방식

     -  작은 문제로 시작해서 큰 문제까지 차례대로 해결하여 최종 문제의 해답을 구한다.

     -  *타뷸레이션 방식으로 테이블에 차례대로 결과를 저장한다.

 

 

 

 

메모이제이션(Memoization) 이란?

 

 

• 컴퓨터가 동일한 계산을 반복 수행 하지 않도록 이전의 계산 값을 메모리에 저장 하였다가 다시 사용하는 기법.
• 메모이제이션은 저장, 재사용, 효율성 이라는 핵심 개념을 가짐.

 

1. 저장 : 계산한 결과를 저장할 자료구조를 사용한다. (배열, 딕셔너리 등)
2. 재사용 및 확인 : 이전의 계산된 결과가 필요한 경우 해당 입력에 대한 결과가 이미 저장되어 있는지 확인 후 재사용 및반환한다.
3. 효율성: 중복 계산을 피하여 시간 복잡도를 줄이고 성능을 향상시킴.

 

 

 

타뷸레이션(Tabulation) 이란?

 

 

 

• 작은 문제부터 차례대로 해결 한 후 그 결과를 테이블에 저장하는 방식
• 저장된 테이블들을 기반으로 문제 해결에 대한 구조를 단계적으로 구축하는 방식
• 상향식 계산 방식으로 때로는 결과 계산에 필요 없는 값까지도 미리 계산해 테이블에 저장하기도 한다.
  (불필요한 계산이 발생하기도 함)
• 재귀문 대신 반복문을 사용하는 경우가 많다. (재귀가 없으므로 스택 오버플로우의 위험성이 없음)

 

 

 

피보나치 수열을 각각 메모이제이션과 타뷸레이션으로 만든 예제

 

 

• 메모이제이션 피보나치 수열

 

class Program
{
    // 메모이제이션을 위한 딕셔너리
    private static Dictionary<int, long> memo = new Dictionary<int, long>();

    static void Main(string[] args)
    {
        int n = 20; // 피보나치 수열의 n번째 수를 구하고자 함
        long result = Fibonacci(n);
        Console.WriteLine($"Fibonacci({n}) = {result}");
    }

    // 피보나치 수열을 계산하는 함수
    static long Fibonacci(int n)
    {
        if (n <= 1)
        {
            return n;
        }

        // 이미 계산된 값이 있는 경우
        if (memo.ContainsKey(n))
        {
            return memo[n];
        }

        // 계산되지 않은 경우 계산 후 저장
        memo[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
        return memo[n];
    }
}

 

 

• 반복되는 계산 값을 메모이제이션 구축을 위한 딕셔너리에 저장하여 재사용하는 방식이다.
• memo 딕셔너리에 n번째 피보나치 수가 계산이 되어있는지 확인 한다.
• 계산 되었다면 해당 값을 return하고 계산되지 않았다면 재귀적으로 해당 값을 계산 후 memo 딕셔너리에 저장한다.

 

 

 

 

• 타뷸레이션 피보나치 수열

 

 

class Program
{
    static void Main(string[] args)
    {
        int n = 40; // 피보나치 수열의 n번째 수를 구하고자 함
        long result = Fibonacci(n);
        Console.WriteLine($"Fibonacci({n}) = {result}");
    }

    static long Fibonacci(int n)
    {
        // 테이블 초기화
        long[] dp = new long[n + 1];

        
        dp[0] = 0;
        if (n > 0)
        {
            dp[1] = 1;
        }

        // 작은 문제부터 차례대로 해결
        for (int i = 2; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

 

 

 

• 타뷸레이션 사용(피보나치 수 저장)을 위한 테이블(배열) dp를 선언하고 초기화한다.
• 피보나치 수열에서 0번째와 1번째 값은 고정이기에 해당 값은 미리 선언한다.
• 이후 반복문을 사용하여 작은 문제의 값 부터 차례대로 계산 후 계산 결과 값을 테이블(배열)에 저장한다.

 

 

 

 

 

요약

• 타뷸레이션: 반복문을 사용하여 작은 문제부터 차례대로 해결하는 바텀업 방식. 모든 하위 문제를 미리 계산하여 테이블에 저장.
• 메모이제이션: 재귀를 사용하여 큰 문제부터 해결하면서 중복된 하위 문제의 결과를 저장하는 탑다운 방식. 필요한 하위 문제만 계산하고 저장.

 

 

 

• 해결해야 하는 문제의 특성에 따라서 타뷸레이션과 메모이제이션 중 좋은 접근방식을 판단해야 한다.
• 재귀가 직관적인지 아닌지, 혹은 적합한 메모리 용량에 따라 판단하는 것도 좋은 방법이다.

 

 

 

사진 출처 : https://www.geeksforgeeks.org/dynamic-programming/?ref=gcse

Dynamic Programming or DP - GeeksforGeeks