DP 1차시 : 1,2차원 dp

1. DP?

DP, 즉 다이나믹 프로그래밍(Dynamic Programming)이란, 하나의 큰 문제를 작은 여러개의 문제로 쪼개어 푸는 기법 중 하나입니다. 보통 주어진 초기값을 바탕으로 순차적으로 메모해가면서 푼다고 생각하면 됩니다.

2. 1차원 DP

피보나치 수

가장 유명한 예시는 피보나치 수입니다. 재귀로 구현되는 top-down approach와 for문으로 구현되는 bottom-up approach가 있습니다.

0 1 1 2 3 5 8 13 21 34 55 ...
// top-down
int dp[] : 전부 -1으로 초기화, dp[0]=0, dp[1]=0, dp[2]=1
int fib(int n){
    if(dp[n]!=-1) return dp[n];
    return dp[n]=fib(n-1)+fib(n-2);
}

//bottom-up
int dp[] : dp[0]=0, dp[1]=0, dp[2]=1
for(int i=1; i<=n; ++i){
    dp[i]=dp[i-1]+dp[i-2];
}

두 방식 모두 많이 사용합니다.

연습 문제1

최적의 해 찾아가기

어떠한 상황에서 최적의 해를 찾았을 때, 그 해를 기억합니다.

후에, 어떠한 상황이 다시 왔을 때 기억한 해를 재사용할 수 있습니다.

단, 같은 상황에서의 최적의 해는 모두 같아야 합니다.

boj.kr/1463 번을 보면서 이게 무슨 뜻인지 알아봅시다.

어떠한 정수 X가 놓여진 상황에서 최적의 값은 절대 달라지지 않습니다.