[알고리즘] Dynamic Programming

김수현·2022년 6월 1일

알고리즘

DP란?

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법!
이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
탑다운과 보텀업으로 구성됌

> 문제가 다음의 조건을 만족할 때 사용할 수 있음

최적 부분 구조: 큰문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결 가능
중복되는 문제: 동일한 작은 문제를 반복적으로 해결해야 함

DP방법

- 메모이제이션

한 번 계산한 결과를 메모리 공간에 메모하는 기법
값을 기록해 놓는다는 점에서 캐싱이라고도 함

1. 탑다운

하향식

2. 보텀업

상향식
전형적인 형태
결과 저장용 리스트 = DP테이블

DP활용 예시

- 피보나치 수열

1,1,2,3,5,8,13,21,34,55,89,...

점화식: An = An-1 + An-2, A1=1, A2=1

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]);  //실행결과:12586269025
}

DP문제 예시

> 문제

> 해결 아이디어

public static int[] d = new int[100];	//DP테이블 초기화
public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
    
    //정수 n을 입력받기
    int n = sc.nextInt();
    
    //모든 식량 정보 입력받기
    int[] arr = new int[n];
    for(int i=0; i<arr.length; i++){
    	arr[i]=sc.nextInt();
    }
    
    //DP진행(보텀업)
    d[0]=arr[0];
    d[1]=Math.max(arr[0],arr[1]);
    for(int i=2; i<n; i++){
    	d[i]=Math.max(d[i-1],d[i-2]+arr[i]);
    }
    
    //계산된 결과 출력
    System.out.println(d[n-1]);
}