동적프로그래밍(Dynamic Programming)

동적프로그래밍(Dynamic Programming)

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것

다음과 같이 중복으로 계산하는 것을 줄여줌으로써 조금 더 문제를 빠르게 해결함.

동적프로그래밍 조건

• 작은 문제가 반복이 일어나는 경우
• 같은 문제가 반복으로 구해지는 경우

동적프로그래밍 방법

모든 작은 문제들은 한 번만 풀고 어딘가에 메모해 놓는다.
다시 큰 문제를 풀어나갈때 똑같은 작은 문제를 직면하는 경우 메모한 작은 문제의 결과값을 이용한다. (Memoization 메모이제이션)

구현 (파이썬)

1. Botton-Up (아래서 위로) -> 작은 문제부터 구해나감

def fibonacci(n):
    if n <= 1:               
        return n   
    first = 0
    second = 1
            
    for _ in range(0, n-1):
        tmp = first + second
        first = second
        second = tmp
    return tmpp

2. Top-Down (위에서 아래로) -> 큰 문제부터 작은 문제로 (재귀함수로 구현하는 경우 대부분 top-down)

def fib_Top_Down(n):
    global cntFib2
    
    if memo[n] > 0:
        cntFib2 += 1
        return memo[n]
    
    if n <= 1:      
        memo[n] = n
        return memo[n]
    
    else:
        memo[n] = fibonacci(n-1) + fibonacci(n-2)
        return memo[n] 

memo = [0 for i in range(100)]

구현 (자바)

1. Botton-Up (아래서 위로) -> 작은 문제부터 구해나감

private static int fib2(int n) {
		if (n <= 1) {
			return n;
		}
		
		int first = 0;
		int second = 1;
		int tmp = 0;
		
		for(int i = 0 ; i < n-1; i++) {
			tmp = first + second;
			first = second;
			second = tmp;
					
		}
		return tmp;
	}

2. Top-Down (위에서 아래로) -> 큰 문제부터 작은 문제로 (재귀함수로 구현하는 경우 대부분 top-down)

private static int fib2(int n) {
		if (memo[n] > 0) {
			return memo[n];
		}

		if (n <= 1) {
			memo[n] = n;
			return memo[n];
		}

		else {
			memo[n] = fib2(n - 1) + fib2(n - 2);
			return memo[n];
		}

	}