[알고리즘] 다이나믹 프로그래밍

 

다이나믹 프로그래밍 (Dynamic Programming)

 

큰 문제를 작은 문제로 나눠서 푸는 알고리즘 기법

 

1. Overlapping Subproblem

 - 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.

 - 문제를 작은 문제로 쪼갤 수 있다.

 

2. Optimal Substructure

 - 문제의 정답을 작은 문제의 정답에서 구할 수 있다.

 - 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.

 

• 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 

• Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때 마다 정답이 같다. 

• 따라서, 정답을 한 번 구했으면, 정답을 어딘가에 메모해놓는다.

• 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다.

• 메모를 한다고 해서 영어로 Memoization이라고 한다. 

 

피보나치 수 

Fn = Fn-1 + Fn-2 (n≥2)

 

• 피보나치수(5)를 호출한 경우 어떻게 호출되는지를 나타낸 그림

• 한번 답을 구할 때, 어딘가에 메모를 해놓고, 중복 호출이면 메모해놓은 값을 리턴한다. 

 

import java.util.Scanner;

public class Main {

	static int [] memo = new int[100];
	
	public static int fibonacci( int n ) {
		
		if( n < 2 ) {
			
			return n;
			
		} else {
			
			if( memo[n] > 0 ) {
				
				return memo[n];
				
			} else {
				
				memo[n] = fibonacci( n-1 ) + fibonacci( n-2 );
				return memo[n];
			}
		}
		
		
	}
	
	public static void main( String[] args ) {
		
		Scanner sc = new Scanner( System.in );
		
		int fibo = sc.nextInt();
		
		int result = fibonacci( fibo );
			
		System.out.println( result );
		
	}
}