동적계획법 - DP (Dynamic Programming) 알고리즘

DP, 다이나믹 프로그래밍이란?

 

-> 하나의 문제를 단 한번만 풀도록 하는 알고리즘 설계 기법입니다. 

---

Why DP를 사용할까?

그냥 사용하면 사실 재귀방식과 똑같이 사용할 수 있다. 하지만, 일반적인 코딩테스트 같은 경우 시간제한이 걸려있기 때문에 동일한 작은 문제를 여러번 풀면 무조건적으로 시간초과가 뜨게 된다. 

 

예를 들어, 피보나치 수열을 그 예로 들 수 있다.

#include <iostream>

int dp(int x){

	if( x == 1) return 1;
    if( x == 2) return 1;
    
    return dp(x - 1) + dp ( x - 2);
    
 }

 

위 처럼 코딩을 하게 된다면, 50번째만 가도 굉장히 오래 걸리게 된다. 

 

#include <iostream>

int d[100];

int dp(int x){

	if ( x == 1) return 1;
    if ( x == 2) return 1;
    if (d[x] != 0 ) return d[x];
    return d[x] = dp(x - 1) + dp(x - 2);
    
}

int main(){
 std::cout << dp(50);
}

 

반면 위처럼 코딩을 하게 된다면, 내가 이미 거쳐간 계산은 다시 연산할 것 없이 d[] 라는 배열에 저장을 해놓기 때문에 다음번에 계산할 때는 여기서 꺼내쓰면 된다. 

 

즉, DP를 쓴다면 반복 계산 과정이 줄어들어 엄청나게 시간이 절약된다는 것이다. 

 

---

 

그렇다면, 동적 계획법은 어떨 때 쓸 수 있는 것인가?

 

DP를 사용할 수 있는 조건

1. 큰 문제를 작은 문제로 나눌 수 있을 때 ( 중복되는 부분 문제)

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때 (최적 부분 구조)

 

① 중복되는 부분 문제

 

DP는 기본적으로 중복되는 문제의 값을 재활용해서 전체의 답을 구하는 것이다. 그래서 동일한 작은 문제들이 반복할 때 사용이 가능하다.

 

즉, DP는 문제를 재계산할 경우에 사용이 가능한데, 이러한 문제가 반복되지 않는다면 사용이 불가능하니 주의하여야 한다. 

 

② 최적 부분 구조

 

 

작은 문제 (부분 문제)의 최적 결과 값이 전체 문제에서 최적의 결과값을 낼 수 있어야 한다. 

 

최적의 경로 찾기

 

즉 위의 그림과 같이 Start 지점에서 2번째 지점으로 갔을 때, 2번째 지점에서 3번째 지점으로 가는 경우의 수가 다 다르다면 DP를 사용할 수 없다. 만약 위의 그림이 start 지점에서 3가지 경우가 하나의 지점으로 몰리고, 2번째  지점에서 goal 가게 된다면 DP가 가능한 것이다. 

 

---

 

코딩테스트 DP 문제 모음 

 

 

[백준/C++] 1149번 RGB 거리 (DP)

 

 

 

[백준/C++] 9095번 1,2,3 더하기 (DP 문제)

 

 

[백준/C++] 2579번 계단 오르기 (DP 문제)

 

 

[백준/C++] 11659번 구간 합 구하기 4 (DP)