[알고리즘] 동적 프로그래밍

완전 탐색의 문제점

완전 탐색은 가능한 모든 경우의 수를 탐색하는 방법입니다. 서로 다른 여러 경우의 수를 탐색하는 데 중복된 과정이 필요할 때는 해당 과정을 여러 번 연산하게 됩니다. 이러한 중복 과정이 많으면 많을수록 탐색 과정은 매우 비효율적입니다.

 

피보나치 수열은 하나의 항이 이전 두 항의 합으로 나타나는 수열로, 그 점화식은 아래와 같습니다.

F(n) = F(n-1) + F(n-2) F(0) = 0 F(1) = 1

 

이를 재귀 함수로 구현하면 다음과 같습니다.

private static long fibonacci(int n) {
	if (n == 0 || n == 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

위 그림과 같이 이미 했던 연산을 계속해서 반복하게 됩니다. 이를 코드로 나타내면 아래와 같습니다.

package ch01.sec01;

public class Main {
    private static int calls = 0; // 메서드 호출 횟수를 저장하는 변수

    public static void main(String[] args) {
        System.out.println(fibonacci(5));
        System.out.println("호출 수: " + calls);
    }

    private static long fibonacci(int n) {
        calls++; // 호출 횟수 증가

        if (n == 0 || n == 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

그렇다면 fibonacci(10)의 경우는 어떨까요?

기하급수적으로 호출 수가 증가하는 것을 확인할 수 있습니다. 이를 해결하고자 쓰이는 게 동적 프로그래밍입니다.

 

동적 프로그래밍이란?

동적 프로그래밍은 동적 계획법이라고도 하는데요. 작은 문제들을 풀면서 그 결과를 저장해 나아가며 전체 문제를 해결하는 알고리즘입니다. 중복 계산을 줄여서 계산 속도를 높일 수 있으며 경우의 수가 많은 경우에도 효율적으로 계산할 수 있습니다. 일반적으로 재귀적으로 구현되며 메모이제이션(Memoization) 기법을 사용하여 중복 계산을 피합니다. 

 

메모이제이션이란?

한번 풀었던 부분 문제에 대한 답을 저장해 놓았다가 해당 부분 문제를 다시 풀 일이 생기면 재사용하는 것입니다.

위 그림에서는 재귀를 이용하여 직접 계산한 결괏값은 위쪽, 한번 풀어 본 문제의 정답은 화살표로 이어 재사용하였습니다. 쉽게 확인할 수 있듯이 fibo(3)과 fibo(2)는 중복이 발생하므로 한번 문제를 해결한 이후에는 재귀를 더욱 깊숙이 내려가지 않고 바로 부분 문제의 답을 반환합니다. 재귀 구현에 메모이제이션을 적용하려면 다음 과정을 거쳐야 합니다.

1. 문제에서 제시된 범위에 따라 메모이제이션 배열 선언과 초기화

메모이제이션을 하기 위해서는 답을 기록할 배열이 필요합니다. 메모이제이션 배열은 상태에 포함된 변수들을 사용하여 메모이제이션 배열을 참조하면 그 값이 해당 상태가 나타내는 부분 문제에 대한 답이 되는 구조입니다.

 

피보나치 수 문제의 경우 상태는 n 하나이므로 메모이제이션 배열은 1차원 배열이 됩니다. 또 부분 문제의 답은 피보나치 수이므로 long형의 배열이 됩니다. 이 경우에서는 최대 100까지 입력된다고 가정하면 메모이제이션 배열은 아래와 같습니다.

private static final long[] mem = new long[101];

 

이렇게 메모이제이션 배열을 선언한 후에는 반드시 초기화를 해야 합니다. 가장 처음에는 아무런 부분 문제도 해결하지 않은 상황이기 때문에 부분 문제를 풀지 않았다는 것을 나타내야 합니다. 

 

0 이상의 정수는 피보나치 수가 될 가능성이 있으므로 절대 피보나치 수가 될 수 없는 -1로 채워 줍니다. 이는 재귀 호출을 실행하기 전인 main() 메서드 가장 위에서 합니다.

Arrays.fill(mem, -1);

 

2. 재귀의 종료 조건에 메모이제이션 추가

이미 풀어 본 문제는 다시 풀 필요가 없으므로 메모이제이션 된 부분 문제의 경우 메모이제이션되어 있는 값을 사용하도록 종료 조건을 추가합니다. 메모이제이션 조건과 기존에 있던 종료 조건의 순서는 문제마다 다르게 적용할 수 있습니다. 종료 조건에서 비용이 큰 연산이 있다면 메모이제이션 검사를 우선으로 하는 것이 좋습니다. 하지만 종료 조건이 불가능한 상태를 검사하는 것이라면 기존 종료 조건을 먼저 검사해야 합니다.

 

예를 들어 메모이제이션 배열에 -1처럼 유효하지 않은 인덱스로 접근할 수 있는 상태는 기존 종료 조건을 이용하여 먼저 걸러 주어야 합니다. 피보나치 수열의 경우 연산 비용이 높지 않고 유효하지 않은 상태가 입력으로 들어오지 않으므로 메모이제이션 검사와 기존 종료 조건 사이의 순서는 상관없습니다.

if (mem[n] != -1) return mem[n];
if (n == 0 || n == 1) return n;

3. 부분 문제에 대한 답을 구한 후 메모이제이션 배열에 기록

메모이제이션되어 있지 않은 부분 문제를 풀고 난 후에는 그 답을 기록하여 이후에 같은 부분 문제를 풀 때 재사용해야 합니다.

return mem[n] = fibonacci(n - 1) +  fibonacci(n - 2);

 

메모이제이션 배열은 다음 그림과 같이 부분 문제의 답을 배열 형태로 저장해 놓습니다.

이제 피보나치 수를 구하는 메서드에 메모이제이션을 적용한 코드가 완성되었습니다.

package ch01.sec01;

import java.util.Arrays;


public class Main {
    private static int calls = 0; // 메서드 호출 횟수를 저장하는 변수
    private static final long[] mem = new long[101]; // 메모이제이션 배열 선언

    public static void main(String[] args) {
    	Arrays.fill(mem, -1); // 메모이제이션 배열 선언
        System.out.println(fibonacci(10));
        System.out.println("호출 수: " + calls);
    }

    private static long fibonacci(int n) {
        calls++; // 호출 횟수 증가
        
        if (mem[n] != -1) return mem[n]; // 종료 조건에 메모이제이션 추가
        if (n == 0 || n == 1) return n;

        return mem[n] = fibonacci(n - 1) + fibonacci(n - 2); // 메모이제이션 배열에 부분 문제에 대한 답 기록
    }
}

 

기존에 177번이었던 재귀 호출 횟수가 19번으로 굉장히 크게 감소했습니다. 이는 부분 문제가 더 많이 발생할수록 그 효과가 커집니다. 예를 들어 n = 50일 때는 재귀가 2,075,316,483번으로 20억 번이 넘어가는 반면, 메모이제이션을 적용했을 때는 99번으로 엄청난 차이를 보입니다.

 

동적 프로그래밍의 조건

1. 최적 부분 구조

큰 문제의 최적해가 작은 문제의 최적해를 포함하는 성질입니다. 즉, 작은 문제의 최적해를 구한 후 그것을 이용하여 큰 문제의 최적해를 구할 수 있습니다.

2. 중복 부분 문제

동일한 작은 문제를 반복적으로 해결해야 하는 성질입니다. 즉, 작은 문제를 해결할 때 반복적으로 같은 문제를 해결해야 합니다.

 

동적 프로그래밍의 종류

종류	특징	장점	단점
탑다운(Top-Down) 방식	큰 문제를 해결하기 위해 작은 문제를 호출하는 방식	작은 문제들의 결과값을 저장함으로써 동일한 계산을 반복하지 않아 시간 복잡도가 감소합니다.	스택 오버플로우 발생 가능성이 있습니다.
바텀업(Bottom-Up) 방식	작은 문제부터 차례대로 해결해 나가는 방식	부분 문제의 해를 저장하고 이를 활용하여 다음 문제를 해결함으로써 시간 복잡도가 감소합니다.	초기값을 설정해 줘야 하고, 작은 문제들의 결과값을 임시적으로 저장해 둘 공간이 필요합니다.

탑다운(Top-Down) 방식

재귀적으로 호출하여 문제를 해결하는 방식입니다. 재귀 호출을 사용하므로 스택 오버플로우 문제가 발생할 수 있습니다. 큰 문제를 작은 문제로 나누어 푸는 분할정복 방식과 비슷합니다. 다만 중복되는 작은 문제들을 한 번만 푸는 것이 특징입니다.

[탑다운 방식을 이용하여 피보나치 수열을 계산하는 방식] 1. dp 배열을 메모이제이션용으로 사용하여 이전에 구한 값을 저장하고 중복 계산을 방지합니다. 2. n이 1보다 작거나 같은 경우에는 n을 반환하고, 그 외의 경우에는 fib(n-1)과 fib(n-2)를 더한 값을 dp 배열에 저장한 후 반환합니다.

public class TopDownDP {
	static int[] dp = new int[100];
    
    public static int fib(int n) {
    	if (n <= 1) {
        	return n;
        }
        if (dp[n] != 0) {
        	return dp[n];
        }
        db[n] - fib(n-1) + fib(n-2);
        return dp[n];
    }
    
    public static void main(String[] args) {
    	int n = 10;
        System.out.println("fibonacci(" + n + ") =  " + fib(n));
    }
}

바텀업(Bottom-Up) 방식

작은 문제부터 해결하여 큰 문제까지 해결하는 알고리즘 방식입니다. 이 알고리즘의 핵심은 이전에 계산한 부분 문제의 결과를 저장해 두고 나중에 같은 부분 문제가 나타날 때 다시 계산하지 않고 저장된 값을 사용하여 시간을 절약합니다. 해당 방식은 탑 다운 방식과 비교하여 재귀적으로 수행하지 않고 반복문을 통하여서 문제를 해결해 나아가는 방식을 의미합니다.

[바텀업 방식] 1. memo[0]과 memo[1]은 초기값으로 설정합니다. 2. i가 2부터 n까지 반복문을 통해 memo[i] = memo[i-1] + memo[i-2]로 값을 계산하고 저장합니다. 3. 이를 통해서 n번째 항의 값을 반환합니다.

public int fibonacci(int n) {
	if (n <= 1) {
    	return n;
    }
    int[] memo = new int[n+1];
    memo[0] = 0;
    memo[1] = 1;
    for (int i = 2; i <= n; i++) {
    	memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
}

탑다운 방식과 바텀업 방식은 동일한 게 아닌가?

아닙니다. 둘 다 동일한 계획적 탐색의 종류 중에 하나지만 각각 해결 방식이 다릅니다. 탑다운 방식은 작은 부분 문제를 재귀적인 호출을 이용하여서 해결하는 방식입니다. 바텀업 방식은 작은 부분 문제부터 시작하여 반복문을 통해 해를 계산하고 저장해둔 뒤 이전에 계산 문제의 해를 점점 더 큰 문제로 해결하는 방식입니다.

 

동적 프로그래밍 VS 분할 정복

최적 부분 구조는 분할 정복 방식으로 풀 수 있습니다. 동적 프로그래밍과 분할 정복은 해당 문제가 최적 부분 구조의 조건을 가질 때 사용할 수 있습니다. 상위 문제를 하위 문제로 나누어 해결하는 방식으로 처리하면 됩니다.

하지만, 차이점은 하위 문제의 중복입니다.

하위 문제가 독립적이지 않고 중복이 되는 경우에는 동적 프로그래밍의 방식이 분할정복보다는 더 나은 시간복잡도를 가집니다. 왜냐하면 분할정복에서는 동일한 하위 문제는 각각 독립적으로 구성되어 있기 때문에 반복적으로 계산이 되지 않기 때문입니다.