C# - 다이나믹 프로그래밍(DP)

다이나믹 프로그래밍

메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작은 부분 문제로 나누어 해결하며 이미 계산된 작은 문제의 결과를 메모리에 저장(메모제이션)하여 중복 계산을 피하는 방식으로 동작한다.

 

메모제이션(Memoization)이란?

한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 값을 기록해 놓는다는 점에서 캐싱(Cahcing)이라고도 한다.

 

다이나믹 프로그래밍이기 위한 조건 2가지

1) 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있어야 한다. 

2) 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결할 수 있어야 한다. 

 

다이다닉 프로그래밍 크게 두 가지 구현 방식으로 나뉜다. 탑다운방식과 보텀업 방식이다.

---

탑다운 방식

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 하향식 방법이라고도 한다.  탑다운 방식은 재귀(Recursion)를 기반으로 하며 필요한 부분 문제의 해를 메모리에 저장하는 방식이다. 이미 계산된 결과가 메모리에 저장되어 있으며 중복 계산을 피하고 저장된 결과를 반환한다. 결과 저장용 리스트는 DP 테이블이라고도 부른다.

---

예시

01 탑다운 방식을 사용하지 않는 경우 피보나치 수열

점화식이란 인접한 항등 사이의 관계식을 의미한다. 피보나치 수열을 점화식으로 표하면하면 다음과 같다.

재귀를 이용하면 쉽게 표현할 수 있다.

public static int fibo(int x)
{
    if (x == 1 || x == 2)
        return 1;
    return fibo(x - 1) + fibo(x - 2);
}

여기에서 문제가 생긴다.

만약 f(6)이라면 f(2)가 여러번 호출되는 중복문제가 발생된다.

-> 그러므로 별도의 공간에 해결된 문제들을 모아놓아야한다.

---

02 탑다운 방식을 이용한 경우

static int[] FF = new int[1000];

public static int fibo(int x)(탑다운 다이나믹 프로그래밍)
{
    if (x == 1 || x == 2)
        return 1;
    if (FF[x] != 0) // 이미 계산한 적 있는 문제라면 그대로 반환
        return FF[x];
    FF[x] = fibo(x - 1) + fibo(x - 2); // 아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
    return FF[x];
}

실행 결과

이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리할 것을 기대할 수 있다.

메모제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N)이다.

---

보텀업 방식

작은 부분 문제부터 시작하여 피료한 모든 부분 문제의 해를 순차적으로 해결해 나가는 방식이다. 주로 반복문을 사용하여 구현되며 DP테이블에 결과를 저장하면서 중복 계산을 피한다.

long[] FF = new long[100];
FF[1] = 1;
FF[2] = 1;
int N = 50;

// 피보나치 함수 반복문으로 구현(보텀업 다이나믹프로그래밍)
for(int i = 3; i < N+1; i++)
{
    FF[i] = FF[i - 1] + FF[i - 2];
}
Console.WriteLine(FF[N]);

---

다이나믹 프로그래밍과 분할정복은 모두 최적 부분 구조를 가질 때 사용할 수 있는 알고리즘 기법으로 큰 문제를 작은 문제로 나누어 해결하는 공통점이 있다. 하지만 기법 간에는 부분 문제의 중복 처리에 대한 부분은 다르다.

 

다이나믹 프로그래밍(Dynamic Programming)

작은 부분 문제들이 서로 영향을 미치며 중복이 발생한다. 이전에 계산한 부분 문제의 해를 저장하고 필요할 때 재활용하여 중복 계산을 피한다. 메모제이션이라는 기법을 사용한다.

예시 : 피보나치 수열

 

분할 정복(Divde and Conquer)

동일한 문제가 반복적으로 계산되지 않는다. 각 부분 문제는 서로 독립적이며 중복이 발생하지 않는다.

예시 : 퀵정렬

C# - 퀵 정렬(Quick Sort)