Dynamic Programming

개요

---

동적 계획법(DP)은 하나의 큰 문제를 작은 문제로 나누어서 그 결과를 저장 후 다시 재활용하는 방식으로 특정된 알고리즘이 아니라 하나의 문제 해결 방법론이며, 아래 조건을 만족할 때 사용할 수 있다.

1. 최적 부분 구조(Optomal Substructure)
2. 겹치는 부분 문제(Overlapping Subproblems)

 

 

동작 원리

---

 

DP는 일반적인 재귀 방식과 매우 유사하다. 만약 피보나치 수열을 재귀 방식으로 푼다면 작은 문제들이 여러번 반복되어 비효율적인 계산이 될 수 있지만 한 번 구한 작은 문제의 결과 값을 저장하여 재사용한다면 앞서 계산된 값을 다시 반복할 필요가 없어 보다 더 효율적으로 문제를 해결할 수 있다.

시간복잡도 기준 O(n^2) -> O(f(n))으로 개선 가능하다.(문제 별 상이)

 

문제 해결의 대표적인 예로 피보나치 수열 구하기가 있다.

먼저 일반적인 재귀 방식으로 문제 접근 시 아래와 같이 점화식을 작성하여 이를 토대로 코드에 적용하여 풀 수 있다.

• *점화식 : 인접한 항들 사이의 관계식

  

  

    
    
    
    
  
public class fibonachi{
	public int[] fiboArr(int num){
    	if(num==1 || num==2) return 1;
    	return fiboArr(num-1) + fiboArr(n-2);
    }
}

이 경우 아래 이미지에서 볼 수 있듯이 f(2)가 중복되어 여러번 호출되기 때문에 불필요한 연산이 반복된다.

이를 개선하기 위해 메모이제이션을 사용할 수 있으며 아래 구현 방식에서 자세히 살펴보자.

 

 

구현 방식

---

Memoization(메모이제이션)

• 메모이제이션은 한 번 계산한 결과를 메모리 공간에 메모한다는 뜻으로 미리 결과를 저장할 배열을 만들고 변수 값에 따른 결과가 나올 때마다 배열 내에 저장&재사용하는 방식으로 문제를 해결한다.
  • *값을 저장할 때 보통 배열 사용(변수의 개수에 따라 배열의 차원 상이)
  • *값을 기록해놓기 때문에 캐싱(caching)이라고도 함 
  • *메모이제이션은 DP를 구현하는 방법 중 하나일 뿐 DP에만 국한된 개념이 아님

 

Top-Down(Memoization)

• dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.

  

    
    
    
    
  
public class TopDown{
	static int[] fibo;
    public static void main(String[]args) throws IOExeption{
    	BufferReader br = new Buffereader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        fibo = new int[num+1];
        System.out.println(fibonacci(num));
    }
    
    public static int fibonacci(int num){
    	if(num==1 || num==2) return 1;		//종료 조건
        if(fibo[num]!=0) return fibo[num];		//이미 계산한 적 있으면 그대로 반환
        fibo[num] = fibonacci(num-1) + fibonacci(num-2);
        return fibo[num];
    }
}

 

Bottom-Up(Tabulation)

• DP를 설계하는 전형적인 형태로, 반복을 통해 dp[0]부터 하나 하나씩 채워 이 Table에 저장된 값에 직접 접근하여 재활용하는 방식이다.

  

    
    
    
    
  
public class BottomUp{
	static int [] fibo;
    public static void main(String[]args) throws IOExeption{
    	BufferReader br = new BufferReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine);
        fibo = new int[num+1];
        System.out.println(fibonacci(num));
    }
    public static int fibonacci(int num){
    	fibo[1] = 1;	//가장 하위 상태를 미리 저장
        fibo[2] = 1;
        for(int i=0; i<num+1; i++){		//반복문을 사용하여 table을 채워나감
        	fibo[num] = fibo[num-1] + fibo[num-2];
        }
        return fibo[num];
    }
}

 

 

 

그리디 알고리즘과의  비교

---