[이코테 with Java] 다이나믹 프로그래밍

다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 복잡한 문제를 간단한 하위 문제로 나누어 풀고, 그 결과를 저장하여 중복 계산을 방지하는 기법이다. 다른 말로 동적계획법이라고도 한다.

 

이 기법은 주로 다음 조건을 만족할 때 사용할 수 있다. 

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

다이나믹 프로그래밍에는 대표적으로 2가지 방식이 있다. 

첫 번째 방식은 탑다운이고, 두 번째 방식은 보텀업이다.

 

다이나믹 프로그래밍에 대해 알아보기 전에 기존의 알고리즘으로 해결하기 어려운 문제 중에서 다이나믹 프로그래밍으로 해결할 수 있는 문제를 살펴보자. 

 

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다.

피보나치 수열이란 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 

 

1          1           2            3           5          8           13
                         ^             ^           ^          ^             ^
                       1+1         1+2       2+3     3+5        5+8

 

수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게 표현한다.

점화식이란 인접한 항들 사이의 관계식을 의미한다. 

 

예를 들어 수열 {an}이 있을 때 수열에서 각 항을 an이라고 부른다고 가정하자.

 

이러한 점화식은 인접 3항간 점화식이라고 부르는데 인접한 총 3개의 항에 대해서 식이 정의되기 때문이다. 

피보나치 수열에서는 첫 번째 항과 두 번째 항의 값이 모두 1이기 때문에 최종적으로 피보나치 수열을 나타낼 때에는 다음과 같이 정의할 수 있다.

• n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2) 번째 피보나치 수
• 단, 1번째 피보나치수 = 1, 2번째 피보나치 수 = 1

프로그래밍에서는 이러한 수열을 배열이나 리스트로 표현할 수 있다. 

수열이란 여러 개의 수가 규칙에 따라서 배열된 형태를 의미하는 것이기 때문이다. 

 

수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 사용하면 간단하다.

첫 번째로 피보나치 함수를 재귀 함수로 구현한 것을 보여주겠다.

 

1. 재귀 함수로 표현

import java.util.*;

public class Main {

    // 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
    public static int fibo(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }
        return fibo(x - 1) + fibo(x - 2);
    }

    public static void main(String[] args) {
        System.out.println(fibo(4));
    }
}

 

첫 번째로 fibo(4)를 호출하면 fibo(3) + fibo(2)가 호출된다.

두 번째로 fibo(3)을 호출하면 fibo(2)와 fibo(1)이 호출되며, 1과 2는 1을 반환한다.

따라서 fibo(2) + fibo(1) + fibo(2) = 1 + 1 + 1 = 3이 된다. 

 

피보나치 수열을 소스코드를 이렇게 작성하면 심각한 문제가 생길 수 있다. 

바로 f(n) 함수에서 n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어나기 때문이다. 

빅오 표기법을 이용하면 O(2^N)이 소요된다고 할 수 있다.

 

만약 fibo(6)을 호출한다면 어떻게 될까?

                               f(6)
                          f(5) + f(4)
                    f(4) + f(3) f(3)+f(2)
              f(3)+f(2)f(2)+f(1) f(2)+f(1)
           f(2)+f(1)

 

f(4)~f(1)까지 반복적으로 호출되는 것을 알 수 있다. 이미 한 번 계산했지만, 계속 호출할 때마다 계산하는 것이다.

이처럼 피보나치 수열의 점화식을 재귀 함수로 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다.

 

따라서 메모이제이션(Memoization) 기법을 활용해 풀 수 있다.

메모이제이션은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 

메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다. 

 

2. 메모이제이션 기법으로 풀이

import java.util.*;

public clas Main {

    // 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화
    public static long[] d = new long[100];

    // 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍) 
    public static long fibo(int x) {
        // 종료 조건(1 혹은 2일 때 1을 반환) 
        if (x == 1 || x == 2) {
            return 1;
        }
        // 이미 계산한 적 있는 문제라면 그대로 반환
        if (d[x] != 0) {
            return d[x];
        }

        // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환 
        d[x] = fibo(x - 1) + fibo(x - 2);
        return d[x];
    }

    public static void main(String[] args) {
        System.out.println(fibo(50));
    }
}

 

프로그램을 실행하면 금방 정답을 도출하는 것을 알 수 있다.

 

정리하자면 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 

사실 큰 문제를 작게 나누는 방법은 퀵 정렬에서도 소개된 적이 있다. 퀵 정렬은, 정렬을 수행할 때 정렬할 리스트를 분할하며 전체적으로 정렬이 될 수 있도록 한다. 이는 분할 정복(Divide and conquer) 알고리즘으로 분류된다, 

다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다. 

 

퀵 정렬을 예로 들면, 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡게 되면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다.

반면, 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결한다는 특징이 있다. 

그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결됐던 것이니까 다시 해결할 필요가 없다고 반환하는 것이다. 

 

3. 탑다운 방식

import java.util.*;

public class Main {

    public static long[] d = new long[100];

    public static long fibo(int x) {
        System.out.print("f(" + x + ") ");
        if (x == 1 || x == 2) {
            return 1;
        }
        // 이미 계산한 적 있는 문제라면 그대로 반환
        if (d[x] != 0) {
            return d[x];
        }
        // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
        d[x] = fibo(x - 1) + fibo(x - 2);
        return d[x];
    }

    public static void main(String[] args) {
        fibo(6);
    }
}

 

이처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을,

큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down)방식이라고 말한다. 

 

반면에 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여

보텀업(Bottom-Up) 방식이라고 한다. 피보나치 수열 문제를 아래에서 위로 올라가는 보텀업 방식으로 풀면 다음과 같다. 

동일한 원리를 적용하되 단순히 반복문을 이용하여 문제를 해결한 것으로 이해하면 된다.

 

 

4. 보텀업 방식

import java.util.*;

public class Main {

    public static long[] d = new long[100];

    public static void main(String[] args) {
        // 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
        d[1] = 1;
        d[2] = 1;
        int n = 50; // 50번째 피보나치 수를 계산

        // 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍) 
        for (int i = 3; i <= n; i++) {
            d[i] = d[i - 1] + d[i - 2];
        }
        System.out.println(d[n]);
    }
}

 

탑다운(메모이제이션) 방식은 '하향식'이라고도 하며, 보텀업 방식은 '상향식'이라고도 한다.

다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

다이나믹 프로그래밍과 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로, 다이나믹 프로그래밍과는 별도의 개념이다. 

한 번 계산된 결과를 어딘가에 담아 놓기만 하고, 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.