[알고리즘] Dynamic Programing(DP / 동적계획법) (Top-Down, Bottom-Up)

Dynamic Programing

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 위키백과

 

 

Dynamic Programing은

1. 하위 문제로 쪼개지며, 하위 문제의 정답으로 해당 문제의 정답을 구할 수 있을 때(Optimal Substructure)

2. 하위 문제가 겹칠 때 (Overlapping Subproblem)

사용할 수 있다.

 

Top-Bottom방식과 Bottom-Up방식이 있는데

이름에서 알 수 있다시피 위에서아래로, 아래에서 위로 가는 방식인 것 같다.

Top-Bottom은 재귀를 통해 메인 문제에서 작은 문제들로 쪼개어가는 과정이고

Bottom-Up방식은 반복문을 통해 쪼개어진 최하단의 문제들로부터 메인 문제를 풀어가는 과정이라고 이해했다.

 

 

(개인적 생각)

DP는 문제를 정의하고, 해당 문제에 따른 하위 문제를 정의하는 것만 잘할 수 있으면 될 것 같다.

 

 

예제 - 피보나치 수열 구하기

---

 

피보나치 수열 7번째의 값을 구하는 과정이다.

위에 적어놓은 대로, 사용할 수 있는지 판단해보자.

 

1.  F(7)을 구하기 위해 하위 문제인 F(6), F(5)..........로 나눌 수 있다.

2. 하위 문제의 결과들로 F(7)을 구하기 위한 F(6)과 F(5)의 값을 알 수 있고, 메인 문제인 F(7)의 결과를 알 수 있다.

3. 하위 문제들이 겹치고 있다.

 

 

코드로 작성해보자.

public int fibo(int n) {
    if(n==0) return 0;
    if(n==1) return 1;

    return fibo(n-1) + fibo(n-2);
}

 

위의 방법처럼 재귀적으로 시도할 경우 구하는 수가 커질 경우 call stack이 overflow가 될 수 있다.

F(10000)을 구한다고 가정해보자.

현재 알고있는 값은 0번째와, 1번째의 값 뿐이기 때문에, 결국 F(1)까지 호출이 되어 순차적으로 해를 구할 수 있는데, 이렇게 되면 stack에 F(10000), F(9999), F(9998) ............... F(1)까지 채워지게되고, 결국 limit을 초과하여 StackOverFlowError가 발생하게 된다.

fibo(10000)을 구하지 못한다.

 

기존 문제는 상위 문제에서 하위 문제로 쪼개어 나가는 방식이었기 때문에 발생했다.

위의 방식을 Top-Down 방식이라고 하며, Top-Down 방식은 재귀적으로 풀어 나간다.

 

이를 해결하기 위해, Bottom-Up 방식의 DP를 적용할 수 있다.

Bottom-Up 방식이란 가장 작은 하위 문제부터 해결해 나가는 방식이다.

 

Bottom-Up 방식은 재귀적으로 해결하는 것이 아닌, 반복문을 사용하여 하위 문제부터 해결해 나간다.

Bottom-Up 방식의 피보나치 수열을 구하는 코드를 작성해보았다.

static List<Integer> list = new ArrayList<Integer>() {{
    add(0);
    add(1);
}};

public int fibo2(int n) {
    if(n==0) return 0;
    if(n==1) return 1;

    for(int i=2; i<n+1; i++) {
        int num = list.get(i-1) + list.get(i-2);
        list.add(num);
    }
    return list.get(n);
}

하위 문제들 부터 풀어나가며, List에 추가한 후, n번째 수를 구하는 코드이다.

top-down과 bottom-up의 속도 차이

 

또한, Top-Down에서는 구하지 못했던 F(10000)의 값도 구할 수 있다.

 

이러한 Bottom-Up방식의 시간복잡도는 O(n)이고, 공간복잡도는 O(n)이지만

공간복잡도는 해당 피보나치 수열을 구하기 위한 F(n-1), F(n-2)만을 필요로 하기 때문에, O(1)까지 줄일 수 있다.

 

 

import java.util.ArrayList;
import java.util.List;

class Solution{
	
	static List<Integer> list = new ArrayList<Integer>() {{
		add(0);
		add(1);
	}};
	
	public int fibo(int n) {
	    if(n==0) return 0;
	    if(n==1) return 1;

	    return fibo(n-1) + fibo(n-2);
	}
	
	public int fibo2(int n) {
	    if(n==0) return 0;
	    if(n==1) return 1;
	    
	    for(int i=2; i<n+1; i++) {
	    	int num = list.get(i-1) + list.get(i-2);
	    	list.add(num);
	    }
	    return list.get(n);
	}
	
        
    
    public static void main(String[] args) {
    	
    	long startTime = System.nanoTime();

		Solution sol = new Solution();
		System.out.println(sol.fibo(40));
		
    	long endTime = System.nanoTime();

    	long durationTimeSec = endTime - startTime;
    	System.out.println("top_down");
    	System.out.println(durationTimeSec + "n/s");
    	System.out.println("ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ");
    	
    	/*********************************************/

    	long startTime2 = System.nanoTime();

		Solution sol2 = new Solution();
		System.out.println(sol2.fibo2(40));
		
    	long endTime2 = System.nanoTime();

    	long durationTimeSec2 = endTime2 - startTime2;
    	System.out.println("bottom_up");
    	System.out.println(durationTimeSec2 + "n/s");
    	System.out.println("ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ");


	}

}