알고리듬 #6 점화식과 동적계획법 : 규칙 찾아내기

이전 글에서는 분할정복(Divide & Conquer) 기법을 학습하였다.
이번 챕터에서는 수학적으로 규칙성(점화식, Recurrence Relation) 을 찾아내어 문제를 최적화하는 기법인 동적 계획법(Dynamic Programming) 을 다룬다.

우선 프로그래밍이라는 것의 본질을 생각해보자.

사실 동적 계획법은 “특정 알고리듬”이라기보다는, 프로그래밍이라는 행위 그 자체와 맞닿아 있는 사고 방식이라 할 수 있다.

세상에는 수없이 많은 문제가 존재한다.

그리고 프로그래밍이란 그것을 컴퓨터로 표현하여 해결하는 과정은 결국 규칙을 찾아 코드화하는 행위이다.

따라서 동적 계획법은 알고리듬 학습 과정에서 반드시 짚고 넘어가야 할 중요한 주제이다.

코딩 테스트 관점에서의 동적 계획법

다만 코딩 테스트라는 제한된 맥락에서 보면 이야기가 조금 달라진다.

동적 계획법이 본래 지닌 “상황에 따라 유연하게 문제를 쪼개고 규칙을 찾아내는 사고” 보다는,
그저 중복 계산을 방지하기 위해 이전 계산 결과를 저장·재사용하는 기법으로 축소되는 경우가 많다

즉, 동적 계획법이 “Dynamic Programming”이라는 본래 이름이 주는 역동성과는 달리,
코딩 테스트에서의 동적 계획법은 사실상 이미 계산된 데이터를 재활용 하는 정적(Static) 기법에 가까워진다.

그래서 개인적으로는 이를 Dynamic Programming이 아니라, 차라리 Dynamic Planning이라고 부르고 싶다.
“규칙을 세워 데이터를 정리해 놓고 상황에 따라 이를 재활용한다”는 의미가 더 정확하게 다가오기 때문이다.

사실 어떻게 보면 항상 유연하게 사고하고, 회고하고, 후회하며 발전하자는 내 인생 철학과도 맞닿아 있는 법칙이긴 하다...

내가 게을러서 안 지켜질 때가 많아서 그렇지...

사담은 이만하고 

점화식이란?

수학적으로는 이번 항과 다음 항, 그리고 그 다음 항... 이렇게 항과 항 사이의 관계를 비교-분석하여 각 항 사이에서 일어나는 변화의 일정한 규칙을 찾아 내어 이를 수식으로 정리하는 것을 말한다.

예시:

• 등차수열 : a(n) = a(n-1) + d
• 등비수열 : a(n) = r * a(n-1)
• 피보나치 수열 : F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1

프로그래밍에서의 점화식

프로그래밍적으로 보면, 수학의 항(term) 이 단순히 데이터로 치환되는 것뿐이다.

즉, 어떤 문제를 작은 단위로 쪼갤 수 있고, 그 관계를 점화식으로 표현할 수 있다면 그대로 코드화하여 해결할 수 있다.

• 재귀(Recursive): 점화식을 그대로 함수 호출로 표현
• 동적 계획법(DP): 중복 계산을 막기 위해 이전 결과를 저장하고 재활용

이전 장에서는 재귀와 분할 정복을 통해 큰 문제를 작은 문제로 나누어 해결하는 일종의 동적 계획법을 학습했다.

이번에는 문제를 나누는 것에 만족하지 않고 이 해결된 문제들을 재활용하는 방법에 대해서 집중한다.

대표적으로 해결된 문제의 재활용 기법이 사용되는 것이 피보나치 수열이다. 

피보나치 수열을 동적 계획법을 통해 빠르게 계산하기

일반적인 경우 다음과 같이 피보나치 수열에 대한 연산을 수행하는데 수행시간이 오래 걸린다. 

Fibonacci(50)을 연산하는데 걸린 시간이 Ryzen7 5700 기준으로 무려 84초가 걸렸다. 

음수가 나온건 오버플로우 발생 때문이니 무시하자 연산 결과가 21억으론 부족한가보다.

알고리듬/6. 점화식과 동적계획법/피보나치수열.c

// 피보나치 수열 점화식
// F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1
#include <time.h>
#include <stdio.h>

int Fibonacci(int n)
{
    if (n == 0 || n == 1)
    {
        return n;
    }

    return Fibonacci(n-1) + Fibonacci(n-2);
}

int main(void)
{
    clock_t start, end;
    start = clock();

    int n = 50;
    int result = Fibonacci(n);
    
    end = clock();
    double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("fibonacci(%d) result : %d\n", n, result);
    printf("running Time : %.15lf sec\n", cpu_time_used);
    return 0;
}

그런데 다음 오는 소스코드를 실행해보자.

알고리듬/6. 점화식과 동적계획법/피보나치수열_DP.c

// 피보나치 수열 점화식
// F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1
#include <time.h>
#include <stdio.h>

#define MAX_SIZE 15000

static long long memoizationArray[MAX_SIZE];

void InitializeFibonacci_DP(long long n)
{
    for (long long i = 2; i <= n; ++i)
    {
        memoizationArray[i] = -1;
    }

    memoizationArray[0] = 0;
    memoizationArray[1] = 1;
}

long long Fibonacci_DP(long long n)
{
    if (memoizationArray[n] != -1)
    {
        return memoizationArray[n];
    }

    long long value = Fibonacci_DP(n - 1) + Fibonacci_DP(n - 2);
    memoizationArray[n] = value;
    return value;
}

int main(void)
{
    clock_t start, end;
    start = clock();

    long long n = 15000;

    InitializeFibonacci_DP(n);
    long long result = Fibonacci_DP(n);
    
    end = clock();
    double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("fibonacci(%%lld) result : %lld\n", n, result);
    printf("running Time : %.15lf sec\n", cpu_time_used);
    return 0;
}

50일때

 

Fibonacci_DP(15000)일 때 : Fibonacci(50)의 약 84,000배의 속도를 자랑한다.

수를 크게 줘봐도 다음과 같이 과도한 함수 호출에 의한 스택 오버플로우가 터지면 터졋지 시간을 잴 수 없을 정도로 빨라진다.

여태까지는 탑-다운(큰 문제를 작은 문제로 분할하여 호출)을 통해 문제를 해결했다. 그러다 보니 아주 큰 문제에 대해서는 함수 호출에 대해 스택 오버플로우가 생기는 문제가 발생했다. 

이것을 해결하는 것은 여러가지가 있지만 가장 기본적인 것은 함수 호출을 안하고 반복문을 통해 원시적으로 해결하는 것이다.

// 피보나치 수열 점화식
// F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1
#include <time.h>
#include <stdio.h>

#define MAX_SIZE 15000000

static long long memoizationArray[MAX_SIZE];

void InitializeFibonacci_loop(long long n)
{
    for (long long i = 2; i <= n; ++i)
    {
        memoizationArray[i] = -1;
    }

    memoizationArray[0] = 0;
    memoizationArray[1] = 1;
}

long long Fibonacci_loop(long long n)
{
    long long value = 0;

    int i = 0;
    while (i != n)
    {
        memoizationArray[i+2] = memoizationArray[i+1] + memoizationArray[i];
        i++;
    }

    return memoizationArray[i];
}

int main(void)
{
    clock_t start, end;
    start = clock();

    long long n = MAX_SIZE;

    InitializeFibonacci_loop(n);
    long long result = Fibonacci_loop(n);
    
    end = clock();
    double cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    printf("fibonacci(%lld) result : %lld\n", n, result);
    printf("running Time : %.15lf sec\n", cpu_time_used);
    return 0;
}

결과 이미지를 보면 스택 오버플로우도 없어졌을 뿐 아니라 함수호출로 인한 오버헤드도 줄어들었으므로 연산 속도가 더 빨라졌다.

다만 이전과 다르게 작은 문제를 먼저 풀고 큰 문제를 해결하려 하므로, 이전 문제는 이미 풀렷다는 가정이 존재해 버리기 때문에 "이미 풀렸으면 활용하라" 라는 재활용의 의미는 사라진다.

이렇게 같은 문제라도 풀이하는 방식에 따라 문제 풀이 수행 속도가 까마득하게 차이가 날 수 있다. 

그래서 메모리 사용량을 "더 많이 들여서"라도 빠르게 문제를 해결할 지, 아니면 제한된 공간에서 적당히 빠르게 처리할 지, 그것도 아니면 공간을 절약하는 대신 느리게 문제를 해결할 지와 같은 것은 상황에 따라, 적당히 타협하여 선택하면 된다.

해당 코드들은 제 깃허브에 있습니다. 유사코드는 제공하지 않습니다.

Workspace/알고리듬 at main · cyphen156/Workspace

Workspace/알고리듬 at main · cyphen156/Workspace