분할정복,동적계획

 

분할 정복법 : 그대로는 해결하기 힘든 문제를 작게 나누어 용이하게 풀 수 있는 문제 단위로 나눈 다음 해결하고 그것들을 다시 합치는 것.

• 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.
• 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
• 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

분할 정복법은 재귀적으로 자신을 호출하면서 그 연산의 단위를 조금씩 줄어가는 방식이다. 이를 테면

function F(x):

   if F(x)가 간단한 연산 then:

       return 연산 결과

   else: x를 x1, x2로 분할

       F(x1)과 F(x2)를 호출

       return F(x1), F(x2)로 F(x)를 구한 값

이런 방식이다.

 

한마디로 "F(x)가 간단하다"라는 조건을 만족할 때까지 문제를 쪼개고 쪼개서 값을 구하자는 것이다.

분할 정복에서 핵심인 "간단한 F(x)"가 어떤 것이냐에 따라 알고리즘의 퍼포먼스가 결정된다.

이 "간단한 F(x)"를 정의하는 것이 난해한 경우도 많다. 

 

함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 되는 단점이 있다. 

 

문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.

 

 

동적 계획법 : 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제 해결 패러다임

동적 계획법을 이해하기 좋은 대표적인 예시로 피보나치 수열이 있다.

 

아래는 직관적인 방법으로 작성한 피보나치수열 코드이다.

int f(unsigned int n)
{
    if(n <= 1)
        return 1;
        else return f(n-1)+f(n-2);
}

여기서 재귀적 피보나치 함수의 문제가 드러난다. 5번째 피보나치수열을 구하기 위해선 다음 그림과 같이 총 15번의 함수 호출이 발생한다.

 

 

숫자가 작을 때는 괜찮지만, 숫자가 커지면 시간공간 복잡도가 지수 스케일로 폭발(Exponential Explosion)하기 때문에 비효율적이다.

게다가 fib(2)의 값을 3번이나 계산한다. 이미 계산해놓은 걸 사용하면 안될까?

바로 이럴 때 동적계획법이 사용된다.

동적계획법은 작은 문제들을 단 한번씩만 계산하고 정답을 저장해놓는다. 그러고는 저장된 정답을 재활용한다.

때문에 거의 대부분 동적계획법에서는 정답을 저장하기 위해 배열이 사용된다.