[알고리즘] 동적 계획법과 분할 정복

---

1. 동적 계획법(Dynamic Programming(DP))이란?

: 처음 계산된 값을 저장(Memoization)하고, 이 값으로 상위 문제를 풀어 나가는 방식(상향식 접근법)입니다.

 

* Memoization(메모이제이션) : 프로그램 실행 시 이전에 계산한 값을 저장하고, 이를 이용해 중복 계산을 하지 않고 전체 실행 속도를 빠르게 하는 기술.

* 상향식 접근법 : 가장 최하위의 해답을 구한 후, 이를 저장해 해당 결과값으로 상위 문제를 푸는 방식

 

---

2. 분할 정복(Divide and Conquer)이란?

: 문제를 가장 작은 사례로 나누고, 각각을 푼 다음(하향식 접근법) 합병하여 문제의 답을 얻는 알고리즘입니다. 일반적으로 재귀함수로 주로 구현(재귀함수를 사용하지 않고, 스택이나 큐를 사용하기도 함)하며, 분할 정복 알고리즘에는 병합 정렬과 퀵 정렬이 있습니다.

 

분할정복의 단점으로는 스택에 다양한 데이터를 보관해야 하므로 스택 오버플로우가 발생하거나, 과도한 메모리를 사용하게 된다는 점이 있습니다.

 

* 하향식 접근법 : 상위의 답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식

 

---

3. 동적 계획법과 분할 정복의 공통점과 차이점

1) 공통점 : 큰 문제를 쪼개서 작은 단위로 나눔

2) 차이점

	동적 계획법	분할 정복
Memoization	o	x
부분 문제 중복	o	x
방식	상향식 접근법	하향식 접근법

 

---

4. 동적 계획법과 분할 정복의 활용 예시

피보나치 수열을 예시로 들어 각각의 알고리즘을 설명해보겠습니다.

f(0) = 0;
f(1) = 1;
f(2) = 1; // f(2) = f(1) + f(0)
f(3) = 2; // f(3) = f(2) + f(1)
f(4) = 3; // f(4) = f(3) + f(2)
f(5) = 5; // f(5) = f(4) + f(3)
f(6) = 8; // f(6) = f(5) + f(4)

피보나치 수열은 위와 같이 첫째 항과 둘째 항을 제외한 모든 항의 값이 바로 그 전 두 항의 합을 한 것입니다.

 

1.동적 계획법

public int fact2_Dy(int data)
{
    int[] numlist = new int[data + 1];
    numlist[0] = 0;
    numlist[1] = 1; //처음 값을 저장
    for (int i = 2; i < data + 1; i++)
    {
        //아래 값부터 더하면서 큰 값을 구하는 방식 = 상향식 접근법
        numlist[i] = numlist[i - 1] + numlist[i - 2];
    }
    return numlist[data];
}

 

2. 분할 정복

public int fact2_Re(int data) //하향식
{
    switch (data)
    {
        case 0: return 0;
        case 1: return 1;
    }
    //재귀함수를 이용해 점점 더 작은 값으로 분할 = 하향식 접근법
    return fact2_Re(data - 1) + fact2_Re(data - 2); 
}