[알고리즘] 동적 프로그래밍, DP(Dynamic Programming)

(나만의)구분 특징

• 문제가 반복적인 작은문제로 이루어짐
• 점화식 도출 필요
• 피보나치 함수

 

알고리즘 작성순서

1. 점화식 도출(반복적 부분을 식으로 표현)
2. Top-down VS Bottom-up 선택
3. 비 반복 부분 존재 시 따로 추가 구현(즉, 비 반복적 부분 + 점화식의 형태)

 

참고

Bottom-Up / Top-Down 비교

• Bottom-Up : 필요한 재료 전부를 미리 준비 후 바구니에 넣고 꺼내어 쓰는 방식 ☞ (바구니=)배열/리스트 등
• Top-Down : 필요한 재료를 그때그때 준비해나가는 방식 ☞ 재귀함수 사용

 

피보나치 수열을 통해 이해하기 

'동적 프로그래밍'이라는 이름이 그리 직관적은 아니라 생각한다. 따라서 해당 알고리즘을 이제 막 접하기 시작했다면 단번에 이해하기 힘들수 있다(사실은 내가 그러했다). 그럴때는 '피보나치 수열'을 통한 접근을 해보는게 어떨까 싶다. 피보나치 수열이 동적 프로그래밍 예시 중 제일 익숙한 알고리즘이 아닐까 싶기 때문이다. 

1, 1,    2, 3, 5, 8, 13, 21, 32, 55 .....

비 반복 구간 + 반복구간(=점화식 구간, (n-2)+(n-1)=n)

 

코드예시

Bottom-Up

public class Fibonacci {
	public static void main(String[] args) {
		// index가 아닌 숫자의 실제 위치(ex: 'num'번째에 위치한 숫자) 
		int num = 10;
		
		System.out.println(bottomUp(num));
	}

	private static int bottomUp(int num) {
		// 준비한 재료를 담아둘 바구니(=배열)
		int[] array = new int[num];
		
		// 비 반복적 부분(점화식 불포함 부분)
		array[0] = 1;
		array[1] = 1;
		
		// 반복문으로 재료 준비
		for(int i=2; i<array.length; i++) {
			array[i] = array[i-1] + array[i-2]; //점화식
		}
		return array[num-1]; // 바구니(=배열)에서 필요한 값만 꺼내옴
	}
}

 

Top-Down(재귀함수)

public class Fibonacci {
	public static void main(String[] args) {
		//index가 아닌 숫자의 실제 위치(ex: 'num'번째에 위치한 숫자) 
		int num = 10;
		
		System.out.println(topDown(num));
	}
    
	private static int topDown(int num) {
		if(num <= 2) { // 비 반복적 부분(점화식 불포함 부분)
			return 1;
		} else {
			return topDown(num-1) // 준비되어 있지 않은 재료 => 즉시 준비시작(재귀함수 사용) 
					+ topDown(num-2);  // 준비되어 있지 않은 재료 => 즉시 준비시작(재귀함수 사용)
		}
	}
}