DP(Dynamic Programming, 동적 계획법)

DP

 

• 정의

크고 복잡한 문제를 여러 개의 부분 문제로 나누어 푸는 방법

 

=> 부분 문제들 풀고 값 저장, 해당 문제 다시 만날 때 재연산하지 않고 저장해둔 값 불러옴

 

 

 

• 조건

1. 부분 반복 문제

부분 문제가 여러 번 재사용되는 경우 (=진행했던 연산이 반복되는 경우)

 

2. 최적 부분 구조

부분 문제에서 구한 최적의 값을 이용해(합산해) 큰 문제의 최적의 값을 구함

 

 

 

• 특징

메모이제이션(Memoization)

: 메모리에 부분 문제 값 저장해나감 → 연산 반복될 시 저장해둔 값 사용

 

=> 주로 배열 사용해 값 저장

 

 

 

• 구현 방법 (예시 - 피보나치 수열)

가장 작은 문제(base case) & 점화식 구한 후, Bottom-up 또는 Top-down 방식으로 구현하기

 

 

 

1. Bottom-up 방식

 

: 반복문을 통해 부분 문제의 값 저장해나가며 큰 문제의 값을 구하는 방식

 

public static int bottomUp(int n){
    //base case
    memo[0]=0; 
    memo[1]=1; 

    for (int i=2;i<=n;i++){
        memo[i]=memo[i-1]+memo[i-2]; //점화식 : 앞의 두 숫자 합산 반복
    }

    return memo[n];
}

 

 

2. Top-down 방식

 

: 재귀 함수를 이용해 큰 문제에서 작은 문제를 호출해가며 값을 도출하는 방식

 

public static int topDown(int n){ 
    
    if (n<=2){ //base case
    	return 1;
    } 
    
    if (n>0){ //이미 메모이제이션 배열에 저장된 값이 있을 때
        return memo[n]; //저장된 값 불러옴
    }

    return memo[n]=memo[n-1]+memo[n-2]; //점화식

}

 

 

 

참고 : 

https://didu-story.tistory.com/220

https://hongjw1938.tistory.com/47