동적 계획법(Dynamic Programming)

1. 재귀 호출과 메모이제이션

문제 제시 : 토끼 수 구하기

문제 조건

• 문제의 내용만 달라졌을 뿐 사실 상 피보나치
• f(n) = f(n-2) + f(n-1)이 성립

피보나치 수열

• Fi : 피보나치 i번째 항을 구하는 함수
• Fi : Fi-2 + Fi-1 → 재귀로 구현

fibo(n)
	IF n<2 : return n //기저조건
	ELSE   : return fibo(n-1) + fibo(n-2) //유도파트

fib(2)의 경우 총 8번의 중복 호출 발생

• 재귀 과정에서 엄청난 중복 호출이 존재
  • fibo(7)에서 fibo(2)가 8번 호출됨.
• 단점을 해결하기 위해 먼저 수행된 결과를 저장해두고 재사용(메모이제이션)

메모이제이션(DP의 핵심!)

• 이전에 게산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술!
  • 일반적인 재귀 시간복잡도 : O(n^2)
  • 메모이제이션을 활용 시 시간복잡도 : O(n)
• 자료구조(객체)-동적 테이블- 에 저장되는 값의 의미를 명확히!
• 함수의 실행결과 표현 ⇒ 함수를 리턴값을 주도록 설계
• Memoization 적용 결과 
•  
• fibo(n) IF n>=2 AND memo[n] = 0 //0은 메모가 안된 상태를 의미 memo[n] <- fibo(n-1) + fibo(n-2) return memo[n]
• memo를 위한 배열을 할당하고, 모두 0으로 초기화 memo[0]을 0으로 memo[1]은 1로 초기화 → 유도되어 계산이 불가한 값은 고정값으로 초기화 ⇒ 기저조건에 대한 처리 ==초기화값은 구현에 따라 다를 수 있다==
• Input이 A였을 때 Output이 B여야한다 라는 점화식 정의가 중요!
• Input은 보통 배열의 Index에 매칭
• Output은 해당 Index의 원소값으로 매칭시키는게 보편적
• 추가적인 메모리 공간이 필요
• 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우(재귀호출로 인한 깊이(depth))가 발생할 수 있다. ⇒ 동적계획법 적용으로 해결

---

2. 동적 계획법

정의

• 그리디 알고리즘과 같이 최적화 문제(최대, 최소)를 해결하는 알고리즘
• 경우의 수를 구할 때 사용하는 알고리즘
• 작은 부분 문제들의 해를 구하고 이를 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결

분할 정복과 동적계획법의 비교

분할정복과 DP의 하향식/상향식 접근방법 비교

동적 계획법의 적용 요건

• 동적 계획법을 적용하려는 문제는 필히 다음과 같은 요건을 가지고 있어야 한다.
  • 중복 부분문제 구조
  • 최적 부분문제 구조

중복 부분문제 구조

• 가장먼저 큰 문제를 해결하기 위해 작은 부분문제로 나눌 수 있어야함
• 적용과정
  1. 동일한 형태의 작은 부분문제 구조
  2. 하향식 접근(재귀)
  3. 상태 공간트리 또한 그려볼 수 있음
  4. 중복연산(계산) 발견 가능
  5. 중복부분을 저장해두고 재사용 설계 가능!
• 하향식을 상향식으로 바꿀 수 있는가? → 기저조건부터 처리
• 재귀호출의 연관성을 점화식(메모이제이션)으로 풀어내는 게 DP
• 전체설명 : DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데 ⇒ 이를 위해 DP는 이미 해결된 작은 문제들의 해를 어떤 저장 공간(table)에 저장하게 된다.

최적 부분문제 구조 (or 경우의 수)

• 최적화의 원칙이란 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것!!
• 최적의 원칙이 적용되지 않는 예 : 최장경로 문제 ⇒ DP로 해결 X, DFS로 해결해야함!

3단계 DP 적용 접근 방법

1. 최적해 구조의 특성을 파악하라
   • 문제를 부분 문제로 나눈다. → 처음에는 하향식(재귀)으로 접근 → 중복 부분문제 구조 파악 (이유는 메모이제이션 적용 위해)
2. 최적해의 값을 재귀적으로 정의하라
   • 부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의
3. 상향식 방법으로 최적해의 값을 계산하라
   • 가장 작은 부분문제부터 해를 구한 뒤 테이블에 저장 ⇒ 테이블에 어떤 것을 저장할건지 정확하게 정의필요!
   • 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.(상향식 방법)

피보나치 수 DP 적용

• 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분구조로 이루어져 있음

1. 문제를 부분 문제로 분할
2. 점화식으로 정의
3. 가장 작은 부분 문제부터 해를 구한다. 결과는 동적테이블에 저장, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구함
4. 유도 계산이 불가한 0항 및 1항과 같은 Case는 초기화 후 적용

동적테이블

피보나치를 통한 재귀와 메모이제이션 비교 코드

//피보나치를 통해 재귀와 메모이제이션을 적용했을 때의 차이를 보여줄 수 있는 코드
import java.util.*;

public class FibonacciTest {
	
	static long totalCnt1, totalCnt2, callCnt1[], callCnt2[], memo[];
	
	private static long fibo1(int n) { //피보나치 n항 구하기
		totalCnt1++;
		callCnt1[n]++;
		if(n<2) return n;
		return fibo1(n-1) + fibo1(n-2);
	}
	
	private static long fibo2(int n) { //피보나치 n항 구하기
		totalCnt2++;
		callCnt2[n]++;
		if(memo[n] == -1) { //메모 되어 있는지 확인하여 메모 안되어 있을 경우에만 수행 후 메모하기
			memo[n] = fibo2(n-1) + fibo2(n-2);
		}
		return memo[n];
	}
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		totalCnt1 = totalCnt2 = 0;
		callCnt1 = new long[N+1];
		callCnt2 = new long[N+1];
		memo = new long[N+1];
		
		Arrays.fill(memo, -1); //메모되지 않은 상태를 나타내는 값으로 초기화
		memo[0] = 0;
		memo[1] = 1;
		
		System.out.println(fibo1(N));
		System.out.println("fibo1 : " + totalCnt1); //재귀방식의 호출횟수
		for(int i=0; i<= N; i++) { //n번째 Call횟수 출력
			System.out.println("fibo1[" + i + "] : " + callCnt1[i]);
		}
		System.out.println("======================================================");
		System.out.println(fibo2(N));
		System.out.println("fibo2 : " + totalCnt2); //메모이제이션 적용 후 호출횟수
		for(int i=0; i<= N; i++) {//n번째 Call횟수 출력
			System.out.println("fibo2[" + i + "] : " + callCnt2[i]);
		}
	}
}