[Algorithm] 다이나믹 프로그래밍(동적계획법, Dynamic Programming)

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

· 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법

· 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시킨다.

· 2가지 방식이 존재한다. 1. 탑다운, 2.보텀업

· 최적해를 구하는데 시간 또는 메모리 공간이 매우 많이 필요한 문제는 컴퓨터를 활용해도 해결하기 어려울 수 있다. 

  이럴 때 사용하면 효과적인 기법이다.

 

▶ 예시 - 피노나치 수열

· 점화식으로 나타낸 피보나치 수열

· 점화식: 인접한 항들의 관계식. 수열의 항이 이어지는 형태를 간결하게 표현.

 

▶ 예시 - 재귀를 사용한 피보나치 소스코드

public class 피보나치_재귀적 {
    public static void main(String[] args){
        System.out.println(fibo(7));
    }
    static int fibo(int x){
        if(x==1 || x==2) return 1;
        else return fibo(x-1) + fibo(x-2);
    }
}

결과

· 문제점: 위와 같은 재귀를 사용한 피보나치 구현은 시간 복잡도가 지수시간 소요 O(2^n)된다.

               n이 커질 수록 수행 시간이 기하급수적으로 늘어날 것이다.

 

· 해결: 다이나믹 프로그래밍을 적용 했을 때 피노나치 수열 알고리즘의 시간 복잡도를 훨씬 낮출 수 있다. O(N)

 

▶ 예시 - 메모이제이션(dp 구현 기법 중 하나)을 사용한 피보나치 소스코드

public class FibonacciWithTopDown {
	static long[] cache = new long[100];

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

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

결과

· 메모이제이션(memoization): 다이나믹 프로그래밍을 구현하는 방법 중 한 가지 종류

   - 한 번 구한 결과를 메모리 공간에 메모하고 같은 식을 다시 호출하면, 메모한 결과를 그대로 가져오는 기법

   - 값을 저장하는 방벙이므로 캐싱이라고도 한다.

   - 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

 

· 메모이제이션은 때에 따라서 배열과 리스트를 제외한 다른 자료형을 사용할 수도 있다. ex) 사전(dict) 자료형

 

· 큰 문제를 작게 나누는 방법은 퀵 정렬 같은 분할 정복과 공통되지만,

 다이나믹 프로그래밍은 문제들이 서로 영향을 미친다는 점에서 다르다.

 

· 다이나믹 프로그램을 사용할 수 있는 조건

   1. 큰 문제를 작은 문제로 나눌 수 있음

   2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일함

   - 피보나치 수열은 위 조건을 만족하는 대표 문제다.

 

▶ 예시 - 피노나치를 dp로 처리했을 때 시간 복잡도가 O(N)임을 보여주기 위해 호출되는 함수를 확인해보자.

public class 피보나치_메모이제이션 {
    public static void main(String[] arsgs){
        //한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
        long []cache = new long[100];
        System.out.println(fibo(7,cache));

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

        return cache[x];
    }
}

결과

· 이처럼 재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 dp을 탑다운방식(Top-Down)이라 한다.

<->

· 보텀업(Bottom-Up) 방식: 반복문을 이용하여 소스코드를 작성하여 작은 문제부터 차근차근 답을 도출하는 방식이다.

 

▶ 예시 - 피보나치 보텀업 방식

public class 피보나치_보텀업 {
    public static void main(String[] arsgs){
        System.out.println(fibo(7));
    }
    static long fibo(int x){
        //한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
        Long []cache = new Long[x];
        //첫 번째, 두 번째 피보나치 수는 1
        cache[0] = 1L;
        cache[1] = 1L;

        //피보나치를 반복으로 구현
        IntStream.range(2,x).forEach(num-> cache[num] = cache[num-1]+cache[num-2]);

        return cache[x-1];
    }
}

· 보텀업 방식에서 사용되는 결과 저장용 리스트를 'DP 테이블'이라고 부른다.

 

· 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지

  해결하고자 하는 부분 문제들의 중복 여부를 확인하자.

 

· 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 방법이다.

 

· 하지만 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있으므로,

  재귀 함수를 이용하는 탑다운 방식보다 보텀업 방식으로 구현하는 것이 권장된다.