[C#, Algorithm] Dynamic Programming(동적 계획법)

■ Dynamic Programming(동적 계획법)

큰 문제를 작은 문제로 나누고, 그 작은 문제의 결과를 저장하여 같은 계산을 반복하지 않도록 하는 알고리즘 기법이다.

1. 중복 부분 문제 (Overlapping Subproblems)
   • 동일한 부분 문제를 여러 번 계산하게 되는 구조.
2. 최적 부분 구조(Optimal Substructure)
   • 문제의 최적해가 부분 문제의 최적해로 구성될 수 있다.

기법	특징
재귀	모든 경우를 완전 탐색.
그라디	항상 가장 좋아 보이는 선택을 한다. 최적해를 보장하지 않을 수 있다.
DP	중복 계산을 피하며 모든 경우를 고려. 항상 최적해를 구한다.

 

DP에는 크게 2가지 구현 방식이 있다. 이 구현 방식을 피보나치 수열을 구하는 문제를 통해 알아보자.

 

1. Top-Down 방식

public int[] Memo = new int[100];

// TopDown (재귀 + 메모이제이션)
// 재귀적으로 문제는 풀되, 이미 푼 문제는 저장
public int RecersiveFiboTopDown(int n)
{
		//base case : F(0) = 0, F(1) = 1
		if (n <= 1) return n;
		
		// 이미 계산된 적이 있다면 반환
		if (Memo[n] != 0) return Memo[n];
		
		// 처음 계산하는 경우
		Memo[n] = RecersiveFiboTopDown(n - 1) + RecersiveFiboTopDown(n - 2);
		return Memo[n];
}

재귀적으로 문제는 풀되, 이미 푼 문제를 저장한다. 따라서 중복 계산을 피할 수 있다.

• 대표적으로 다익스트라의 거리 계산, 최장 공통 부분 수열같은 문제가 있다.

 

2. Bottom - Up 방식

public void RecersiveFiboBottomDown(int n)
{
		Memo[0] = 0;
		Memo[1] = 1;
		
		for (var i = 2; i <= n; ++i)
		{
		Memo[i] = Memo[i - 1] + Memo[i - 2];
		}
}

반복문 + 배열을 사용해 문제를 풀이한다. 작은 문제부터 차례대로 계산하며 위로 쌓아간다.

동적 계산식의 적용 방법은 다음과 같이 진행된다.

1. 문제를 작은 부분 문제로 나눈다.
   • 피보나치에서 F(n)을 구하려면 F(n-1), F(n-2)를 먼저 알아야 한다. 즉 F(n-1), F(n-2)라는 작은 문제로 쪼갤 수 있다.
2. 부분 문제의 정답을 저장할 자료구조(dp 배열 등)를 만든다.
   • 중복 계산을 피하기 위해 계산한 F(n)값을 자료구조에 저장한다.
3. 점화식(이전 상태로부터 현재 상태를 만드는 방법)을 정의한다.
   • 이전 두 항만 있으면, 현재 항을 만들 수 있다. (F(n) = F(n-1) + F(n-2))
4. Top-down 또는 Bottom-up 방식으로 계산한다.