DP 알고리즘

그래프와 양대산맥을 이루는 DP는 코딩테스트 단골문제 이자, 많은 응용이 가능한 알고리즘이다.

1. DP란?

1) Dynamic Programming ?

하나의 문제를 더 작은 문제로 나눈 뒤 이 작은 문제의 계산 결과로부터 원래 문제에 대한 답을 계산하는 방식

• Divide and Conquer과 차이점?
  분할 정복 또한, 하나의 문제를 하위 문제로 분할하는 방식이지만
  i. Divide and Conquer는 하위 문제를 독립적으로 해결한 다음 결합하는 방식
  ii. DP는 하위 문제의 해결책을 저장하고 재사용하는 방식

→ DP는 중복 계산을 최소화하고 최적의 해를 찾을 때 사용

2) 점화식

고등학교 때 '수열'을 배우며, 점화식의 개념을 익혔을 것이다. 수열의 점화식이란 수열의 일반항을 구하기 위해 전항과 다음항 간의 일반화된 식을 나타낸다.

가령, 피보나치 수열의 점화식을 작성하면 다음과 같다.

f(n) = 0 if n=0
f(n) = 1 if n=1
f(n) = f(n-1) + f(n-2) if n>1

※ 재귀함수 ver.

#include <iostream>
using namespace std;

int fibo(int x){
	if(x<=1) return x;
    	return fibo(x-1) + fibo(x-2);
}

int main(){
	int T;
    cin >> T;
    cout << fibo(T);
}

• 5번째 항을 구하기 위해
  F(2) = F(0) + F(1)
  F(3) = F(2) + F(1)
  F(4) = F(3) + F(2)
  F(5) = F(4) + F(3)
• F(2) 값을 구하는 과정이 3번 반복된다. 이는 "비효율적"인 리소스 사용

※ DP ver

#include <iostream>
using namespace std;

int arr[10001];

int Fibo(int x){
	if(x<=1){
    	arr[x]=x;
        return arr[x];
    }
    if(arr[x]!=0){
    	return arr[x];
    }
    arr[x] = fibo(x-1) + fibo(x-20;
    return arr[x];
}

int main(){
	int T;
    cin >> T;
    cout << Fibo(T);
}

• 기존에 계산한 피보나치 수열의 값을 사용