[Algorithm] DP(Dynamic Programming) 다이나믹 프로그래밍 알고리즘

 

다이나믹 프로그래밍(Dynamic Programming) 알고리즘

 

 

다이나믹 프로그래밍은 동적 계획법이라고도 불리며, 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.

 

 

자료구조에서 동적(Dynamic)이란 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다.

 

 

 

DP는 이미 계산된 결과는 별도의 메모리 영역에 저장하고 다시 계산하지 않게 하는 방법이며,

 

 

탑다운(하향식)과 보텀업(상향식)이라는 두 가지 방식이 있다.

 

 

 

 

1. 탑다운(하향식) 방법

 

 

메모이제이션(Memoization)은 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.

 

같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져오며,

 

 

값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.

 

 

 

 

2. 보텀업(상향식) 

 

 

DP의 전형적인 형태는 보텀업 방식이다.

 

 

아래쪽에서부터 작은 문제를 하나씩 해결해나가면서 먼저 계산했던 것들을 활용해 그 다음 문제까지 차례로 해결한다.

 

보통 반복문을 이용한다.

 

 

결과 저장용 리스트는 DP 테이블이라고 부르며, 보통 DP, D, 등으로 표현한다.

 

 

 

 

사실 메모이제이션은 이전에 계산한 결과를 일시적으로 기록해 놓는 개념이라고 넓게 이해할 수 있다.

 

 

따라서 DP에만 국한된 개념은 아니며, 한 번 계산된 결과를 담아 놓기만 하고

 

DP를 위해 활용하지 않을 수도 있다.

 

 

---

 

DP를 사용하기 위한 조건

 

 

1. 최적 부분 구조(Optimal Substructure)

  - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.

 

 

2. 중복되는 부분 문제(Overlapping Subproblem)

  - 동일한 작은 문제를 반복적으로 해결

 

 

 

무슨 말인지 피보나치 수열을 예를 들어 설명하겠다.

 

 

피보나치 수열이란 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ... 이런식으로 An = An-1 + An-2, A1, A2 = 1 로 계산되는 수열이다.

 

 

 

 

4번째 피보나치 수 f(4) 구하는 과정

 

 

 

4번째 피보나치 수인 f(4)를 구하는 과정이다.

 

 

이와 같이 f(4)를 구하려면 f(3)과 f(2)가 필요하다. 이 방식이 반복되므로 조건 2개를 만족시킴을 확인할 수 있다.

 

 

 

 

피보나치는 그 유명한 재귀로 간단히 구현할 수 있다.

 

 

import java.util.*;

public class Main {
	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){
    	System.out.println(fibo(4));
    }
}

 

 

 

그러나 단순 재귀로 피보나치 수열을 계산하면 지수 시간 복잡도 O(2^N)를 가지게 된다.

 

 

그래서 n이 조금만 커져도 많은 소요 시간이 필요하다.

 

 

 

f(6)

 

 

f(6)의 값을 구하고 싶을 때를 살펴보아도 f(2)가 여러번 호출되는 것을 확인할 수 있다.

 

 

 

 

 

따라서 우리는 DP를 활용하여 효율적으로 피보나치를 구현해보겠다.

 

 

 

탑다운 사용

import java.util.*;

public class Main {

	public static int d[] = new int[100];

	public static int fibo(int x){
    	if( x == 1 || x == 2 ){
        	return 1;
        }
        
        if(d[x] != 0)
        	return d[x];
           
	fibo(x - 1) + fibo(x - 2);
        
        return d[x];
    }
    
    public static void main(String[] args){
    	System.out.println(fibo(99));
    }
}

 

 

한번 계산된 값인지 확인하는 과정이 추가되어 계산이 된 값이라면 바로 return 하도록 했다.

 

 

 

 

 

보텀업 사용

import java.util.*;

public class Main{
	
    public static long[] d = new long[100];
    
    public static void main(String[] args){
    	d[1] = 1;
        d[2] = 1;
        int n = 50; // 50번째 피보나치 수를 계산할거임
        
        for(int i = 3; i <= n; i++){
        	d[i] = d[i - 1] + d[i - 2];
        }
        
        System.out.println(d[n]);
    }
}

 

 

 

---

 

 

다이나믹 프로그래밍을 사용하기 위해서는 문제 유형을 잘 파악하는 것이 중요하다.

 

 

먼저 그리디, 구현, 완전 탐색 등으로 해결할 수 있는지 확인한 후

 

 

풀이 방법이 떠오르지 않는다면 DP 사용을 고려해보자.

 

 

혹은 일단 재귀로 구현한 뒤 코드를 개선하는 방향으로 사용할 수 있다.

 

 

 

 

 

 

출처 : [한빛미디어] 이것이 취업을 위한 코딩테스트다https://www.youtube.com/watch?v=5Lu34WIx2Us&t=1495s