[알고리즘] 다이나믹 프로그래밍

다이나믹 프로그래밍(Dynamic Programming)은, 핵심부터 설명하자면, 한 번 수행한 연산을 저장시켜두어, 다음에 해당 연산을 또 해야 할 때 기존의 연산 결과를 이용함으로써, 연산의 중복 수행을 막는 알고리즘입니다. 수행한 연산의 결과를 메모리에 저장시켜 둠으로써, 메모리를 조금 더 사용하긴 하지만 그로 인해 연산 속도를 비약적으로 증가시킬 수 있습니다.

 

다이나믹 프로그래밍 사용의 가장 대표적인 예시가 바로 피보나치 수열 문제입니다. 피보나치 수열이란, 이전 두 항의 합을 현재의 합으로 사용하는 특징을 가지는 수열입니다. 아래의 예시가 바로 피보나치 수열입니다.

 

우선 수학적으로 접근하여 재귀함수로 피보나치 함수를 구현하면, 간단하게 구현이 가능합니다. 

 

class Main {
 
    public static int fibo(int x){
       if(x==0)
           return 0;
       else if(x==1)
           return 1;
       else
           return fibo(x-1) + fibo(x-2);
 
    }
 
    public static void main(String[] args) {
        int i;
        for(i=1;i<=20;i++)
            System.out.print(fibo(i) + " ");
    }
}

20번째 수 까지 결과가 잘 나오는 것을 확인할 수 있습니다. 그런데 문제는 이렇게 재귀함수로 구현하게 되면, 이미 했던 연산을 다시 수행하여야 하는 사태가 벌어진다는 것입니다. 

 

만일 fibo(5) 일 때, 연산을 따라가 보면, 다음의 그림과 같은 과정을 발견할 수 있습니다.

 

색칠을 한 fibo(2)를 구하는 과정이 무려 3번이나 포함되어 있습니다. 이게 단지 fibo(5)를 구할 때의 과정이니, fibo(20)을 구할 때는 말할 것도 없겠죠. 이렇듯, 단순하게 재귀함수를 이용한 풀이는 생각이나 구현은 쉽지만, 굉장히 비효율적이며, 연산 시간도 오래 소요됩니다.

 

그래서 다이나믹 프로그래밍이라는 개념이 도입됩니다. 한 번 계산한 식은 배열에 저장해 두고, 그 배열에 있는 결과를 이용해 이후 연산들을 진행하는 것이죠. 

 

class Main {
 
    static int [] arr = new int [21];
 
    public static int fibo(int x){
       if(x==0)
           return 0;
       if(x==1)
           return 1;
       if(arr[x] != 0)
           return arr[x];
 
       arr[x] = fibo(x-1) + fibo(x-2);
       return arr[x];
    }
 
    public static void main(String[] args) {
        int i;
        for(i=1;i<=20;i++)
            System.out.print(fibo(i) + " ");
    }
}

이렇게 하면 연산량을 엄청나게 줄일 수 있습니다. 아래 그림에서 진하게 표시된 부분만 연산을 하면 되고, 나머지 부분은 이미 만들어놓은 배열에서 결괏값을 가져올 수 있습니다.

 

 배열을 사용하지만, 재귀 함수가 아닌, 반복문을 사용해서도 문제를 해결할 수 있습니다.

 

class Main {
 
    public static void main(String[] args) {
        int i;
        int [] arr = new int [21];
        arr[1] = 1;
        arr[2] = 1;
        for(i=3;i<=20;i++)
            arr[i] = arr[i-1] + arr[i-2];
        for(i=1;i<=20;i++)
            System.out.print(arr[i] + " ");
    }
}

 

위에서 살펴본 재귀를 이용한 다이나믹 프로그래밍처럼 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down) 방식이라고 합니다. 그리고 반복문을 이용한 방법처럼, 작은 문제부터 차근차근 답을 도출해 나가는 방법을 보텀업(Bottom-Up) 방식이라고 부릅니다.