[JAVA] Dynamic Programming

프로그래머스 연습 문제를 바로 들어가기 전에, 동적 계획법과 탐욕 알고리즘은 확실하게 짚고 넘어가야 할 거 같아서 따로 포스팅하기로 했다. 

우선 동적 계획법 알고리즘부터 자세하게 다뤄보자.

---

1. Dynamic Programming?

 

 동적 계획법이란 하나의 큰 문제를 쪼개어 부분적인 부분을 풀어 큰 문제를 해결할 수 있도록 고안된 알고리즘이다. 

개념만 딱 들어보면 분할 정복과 다르지도 않은 것 같지만, 큰 차이점이 존재한다. 분할 정복 알고리즘은 큰 문제를 쪼개어 나온 부분 문제를 전부 해결하여 큰 문제에 대한 정답을 도출할 수 있었다면, 동적 계획법 알고리즘은 이미 도출한 부분 문제의 정답을 저장해놓았다가, 중복의 연산을 해야할 때 이를 스킵하고 저장한 값을 사용하여 좀 더 효율적인 연산이 가능하다.

 

 - 피보나치 수열:

동적 계획법 알고리즘의 기본적인 내용을 설명할 때, 가장 대표적으로 쓰이는 것이 이 피보나치 수열이다.

피보나치 수열은 제2항까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수로 정의된 수열이다.

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

 보통의 경우 피보나치 수열의 n번째 항은 다음의 재귀함수를 통해 구할 수 있다.

---

public static int fibo(int n) {
	if (n < 2)
		return 1;
	else {
		return fibo(n - 1) + fibo(n - 2);
	}
}

 

하지만 이 경우, fibo(n - 1) + fibo(n - 2) 의 재귀함수가 실행될 때 반복적으로 이전에 한번 연산을 한 내용을 다시 반복 수행해야한다. 

이러한 중복을 제거하기 위한 기법이 바로 Memorization이다.

 

2. Memorization

 

 동적계획법 알고리즘은 이미 실행한 연산의 결과값을 어딘가 저장해놓고 사용한다고 말했다. 이러한 데이터의 store와 reuse를 Memorization 이라고 칭한다.

 

3. Top - Bottom과 Bottom - Up 방식

 

1) Top - Bottom:

 연산이 위에서 아래로 진행되는 방식이다. 위 피보나치 코드를 수정해보면,

---

public static int[] fiboArray = new int[100];
public static int fibo(int n) {
	if (n < 2)
		return 1;	
    if(fiboArray[n] == 0) {  //이미 진행했던 연산이 아니라면
		fiboArray[n] = fibo(n - 1) + fibo(n - 2); //연산한 결과를 삽입
	}
		return fiboArray[n]; //fiboArray[n]의 값이 0이라면 삽입 후 리턴, 아니라면 저장한 값 리턴
}

 

위와 같은 방법으로 효과적으로 중복 연산을 제거할 수 있다. 거의 대부분의 재귀함수를 활용한 연산은 Top - Bottom에 속한다고 보면 된다. 큰 문제를 풀 때, 그 부분 문제를 풀지 않았다면 부분 문제를 먼저 해결하러 가는 기법이다.

 

 2) Bottom - Up: 

 반대로 연산이 아래에서 위로, 문제가 해결될 때까지 반복 연산을 하는 방식이다.

---

public static int[] fiboArray = new int[100];
public static int fibo(int n) {
	fiboArray[0] = 0;
	fiboArray[1] = 1;
	for(int i = 2; i <= n; i++) {
		fiboArray[i]  =  fiboArray[i - 1] + fiboArray[i - 2];
	}
	return fiboArray[i];
}
	

---

Dynamic Programming은 큰 문제를 해결할 수 있는 모든 부분 문제의 연산을 일단 검토한 뒤, 최적의 해를 찾아내는 방식이기 때문에, 항상 원하는 최적해를 구할 수 있다는 장점이 있지만, 그 만큼 속도적인 측면에서 느린 알고리즘이다.