[이코테] 동적 프로그래밍(Dynamic Programming) 정리

< 요약 > 

사용 목적 : 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘 작성.

                  => 메모리 공간을 사용하여 연산 속도 비약적으로 증가시킬 수 있음.

 

방법

• 탑 다운(Top down) : 큰 문제를 해결하기 위해 작은 문제를 호출
• 바텀 업(Bottom up) : 작은 문제에서 차근차근 답을 도출

 

---

Ex) 피보나치

 

피보나치의 점화식은 앞선 두 항의 덧셈을 통해 현재의 값을 구하는 것으로

점화식을 사용한다면 다음과 같다.

 

만약 동적 프로그래밍을 사용하지 않고 피보나치 함수의 호출을 확인한다면 다음과 같다. (Java) 

public class Sample {
	public static int fibo(int x) {
    	if(x==1 || x==2) {
        	return 1;
        }
        
        return fibo(x-1) + fibo(x-2);
	}
    
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int f = fibo(x);
        System.out.println(f);	
    }
}

 

만약 이렇게 구현한다고 가정했을 때 6을 넣는다면 아래와 같은 형식으로 fibo(6)의 값이 전해진다.

값을 구하기 위해 이미 해결한 문제를 계속해서 호출할 것이고 이는 O(2^n)의 값이 소요된다.

그렇기에 동적 프로그래밍에서 이를 해결하는데에 사용하는 방법은 바로 메모이제이션 (Memorization 이미 해결한 문제를 저장) 이다.

 

메모이제이션이란 다이나믹  프로그래밍을 구현하는 방법 중 하나로 구현 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 캐싱이라고도 부른다.

 

 

 

메모이제이션을 활용하여 탑 다운 방식으로 피보나치를 다시 구현한다면 다음과 같다.

public class Sample {
	public static int fibo(int x) {
    	// 공간만큼 할당(0을 안쓸 예정이므로 +1)
    	int arr[] = new int[x+1];
        
        if(x==1 || x==2) {
        	return 1;
        }
        if(arr[x]!=0) {
        	return arr[x];
        }
        // 배열에 구현한 값을 저장
        arr[x] = fibo(x-1) + fibo(x-2);
        return arr[x];
	}
    
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int f = fibo(x);
        System.out.println(f);	
    }
}

 

 

바텀업 방식으로 구현한 코드는 다음과 같다. 

public class Sample {
	
    
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int arr[] = new int[x+1];
        
        if(x==1 || x==2) {
        	return 1;
        } 
        
        for(int i=3; i<=x; i++){
        	arr[x] = arr[x-1] + arr[x-2];
        }
    }
}