동적 계획법(다이나믹 프로그래밍, DP)

https://pixabay.com/illustrations/fractal-flame-space-energy-fantasy-1068874/

 문제를 해결하는 데 있어서는 많은 방법이 있습니다. 프로그래밍이란 결국 문제를 해결하는 과정을 순차적으로 나열한 것이라고 봐도 무방하겠지요. 오늘 포스트에서는 동적 계획법, 다르게 말하면 다이나믹 프로그래밍(Dynamic Programming, DP)에 대해 알아봅니다.

 

---

Q. 피보나치 수 구하기

 갑자기 웬 피보나치 수를 구하느냐구요? 동적 계획법을 설명하는 가장 간단하면서도 이 기술을 처음 접하는 사람들이 이해하기 쉬운 문제이기 때문입니다. 위 문제를 구하라고 한다면 대체적으로 아래와 같은 두 가지 방법 중 한 가지를 이용할 겁니다.

// # F[1] = F[2] = 1;

int fibonacci1(int n){ // 재귀 함수를 이용한 방법
    if(n > 2){
        return fibonacci1(n-1) + fibonacci1(n-2);
    }else{
    	return 1;
    }
}

int fibonacci2(int n){ // 반복문을 이용한 방법
    int result,a ,b;
    result = a =  b = 1;
    for(int i = 3; i <= n;++i){
    	result = a + b;
        a = b;
        b = result;
    }
    return result;
}

 이 두 코드는 모두 단점을 가지고 있습니다.

 첫 번째, 재귀 함수를 이용한 방법입니다.

재귀함수의 호출 구조

 위 이미지를 fibonacci1(5)를 호출했을 때 발생하는 구조입니다. 재귀 함수는 쉽게 구현이 가능하지만 스택에 함수 호출이 구조가 계속 쌓인다는 점입니다. Windows에서는 프로그램의 스택을  1MB로 제한하고 스택이 1MB를 넘어갈 경우 오류가 발생하게 됩니다. 더욱이 한 번 계산했던 값을 재사용하지 않고 필요할 때마다 다시 계산하기 때문에 속도 또한 느립니다.

 

 두 번째, 반복문을 이용한 방법입니다.

반복문 이용

 

 처음 두 개의 1은 F[1]과 F[2]라는 초기 값을 가지고 있습니다. 이 두 값을 더해 F[N]에 넣고 이 F[N]과 이전 F[N-1]을 더해 F[N+1]을 만든 구조입니다. 재귀 함수처럼 이미 계산한 값을 호출할 필요가 없으니 속도가 빨라졌군요.

 그러나 이 코드 또한 한 가지 단점이 있습니다. N번 째 피보나치 수를 저장하지 않았기 때문에 다시금 값을 요청하면 계산을 다시 해야 하는 것이죠. 그래서 우리는 메모리를 사용합니다.

---

메모리 이용하기

int fibonacci(int n){
    static int fibo[11] = {0,1, };
	
    if(n < 2) return fibo[n];
    else {
        if(fibo[n]) return fibo[n]; // # 1
        else{
            fibo[n] = fibonacci(n-1) + fibonacci(n-2);
            return fibo[n];
        }
    }
	
}

 이번엔 static 배열을 하나 만들어서 계산된 값을 배열에 넣는 작업을 추가해보았습니다. 이때 호출하는 값이 배열에 저장되어 있다면 그 값을 반환합니다. 만일 fibonacci(5)를 호출하고 이후에 fibonacci(4)를 호출한다면 5를 호출할 때는 계산을 해야 하지만, 이 작업을 마치고 fibonacci(4)를 호출하게 되면 fibonacci(5)를 호출하면 4의 값을 계산 후 보관했으므로 # 1에서 값이 반환됩니다.

 이전 알고리즘에서는 메모리 사용을 하지 않고 단순히 CPU 연산력에만 의존했습니다. 따라서 CPU 속도에 알고리즘의 속도가 절대적인 영향을 끼쳤는데 이번에 소개한 코드를 이용하면 계산된 값에 대해서는 O(1)의 시간복잡도를 가지게 됩니다.

---

동적 계획법

 어느 정도 감이 오셨는지 모르겠습니다. 조금 더 어려운 문제를 보겠습니다. BAEKJOON 1149: RGB거리에 대한 코드를 살펴봅니다.

1149번: RGB거리

 이 문제를 공부하면서 동적 계획법을 조금 더 이해하게 되었습니다. 이 문제를 풀기 전에는 동적 계획법 문제를 접하면 동적 계획법으로 풀겠지 하는 짐작을 가지고는 있어도 다가가기는 힘들었는데, 이 문제가 동적 계획법에 대한 자신감을 가지게 하는 첫 문제가 아니었나 싶습니다.

 사실 이 문제를 접하고 일일이 계산시켜야 할까 싶은 생각이 들었습니다. 그렇습니다. 일일이 계산시킵니다. 이전 많은 다이나믹 프로그래밍 문제를 풀어도 일일이 계산시켜야 한다는 생각이 없었는데 이 문제를 풀고 나서 느낀 한 가지입니다.

 

# DP는 작업들을 작게 쪼개서 일일이 계산한다고 생각해라.

# "메모리를 이렇게까지 많이 쓸까?"란 생각 버려라. DP는 메모리를 버리고 속도를 취하는 방식이다. 만일 이 생각을 했다면 잘하고 있는 것이니 그대로 해라.[# 제대로 나아가면 DP에서 메모리 문제도 해결이 가능하긴 합니다만.. 초기엔 이렇게 생각하는 편이 낫겠죠.]

 

BAEKJOON 2579: 계단 오르기 for C

---

읽을거리

 1MB 스택 관련 포스트

[TIPS 19TH] 07 : 2018.07.16. (월)

# index