[DP] 주식투자

우선 동적 계획법은 현업에서 가장 안쓰이는 알고리즘 중 하나이다.

 

하지만 DP를 활용한 모든 문제가 사고력을 바탕으로 풀도록 설계된 문제가 많기 때문에 

 

대회 입상에서는 가히 필수적이라고 말 할 수 있겠다.

 

동적 계획법은 분할 정복이다.

 

문제를 재귀적 구조를 가진 작은 문제들로 분할을 한 뒤, 그 답을 이용해 더 큰 문제의 답을 찾아 나가는 식으로 푸는 문제이다.

 

쪼갠 작은 문제와 합쳐진 문제 사이의 관계를 [점화식]이라고 하며 이 식을 찾는 것이 DP문제의 핵심이다.

 

예제 문제를 통해 DP 알고리즘을 작성하고 점화식이 무엇인지 더 정확하게 알아보겠다.

 

1. 투자

 

첫줄에 돈 M과 회사수 N이 주어진다.

 

이후에 M줄에 걸쳐서 N번째 회사에 투자했을 때 얻을 수 있는 수익금이 주어진다.

 

해당 정보를 가지고 최대의 수익금을 낼 수 있는 도록 투자해보자

 

예를 들어 다음과 같은 예시가 있을 때

 

4 2

2 3

3 5

4 8

5 9 

 

위와 같은 예시가 있을 때 정답은 2 + 8로 10의 가치가 최대가 된다. 

 

(1열 회사에 1원을 투자하여 2원, 남은 3원을 2열 회사에 투자하여 8원)

 

풀이::

회사에 투자할 때는 1~n원을 투자하는 것 외에 0원, 즉 해당 회사에 투자하지 않는 다는 옵션이 있다.

 

이것을 이용해 다음과 같은 점화식을 세울 수 있다.

 

이전 회사에 n원 투자했을때 최고가치 < 이전 회사에 n-k원 투자했을 때 최고 가치 + 현재 회사에 k원 투자했을 때 최고가치

 

k는 현재 투자금액을 의미하므로 0이 포함된다.

 

tab[n+1][m+1];
arr[n+1][m+1];
complist[n+1];

for(i=1;i<=n;i++) { //n은 회사 수
    for(j=1;j<=m;j++) { //m은 가진 투자 금액
        int max = -9999;
        tab[i][j] = arr[j][i];//
        for(k=0;k<=j;k++) {//k는 가진돈 j중에 현재 회사 i에 투자할 금액
            if(max < tab[i-1][j-k] + tab[i][j]) {
                max = tab[i-1][j-k] + tab[i][j];
                complist[i] = k;
                complist[i-1] = j-k;//최적의 가치 갱신
             }
         }
         tab[i][j] = max;
     }
 }
 
 

 

문제의 풀이방식을 보면 첫회사만 놓고 1원부터 주어진 돈까지의 투자를 해나가며 최적해를 갱신하는 방식으로 정답을 구한다.

 

tab[1][1] = 1번째 회사에 1원을 가지고 투자했을 때 얻을 수 있는 최대치

tab[1][2] = 1번째 회사에 2원을 가지고 투자했을 때 얻을 수 있는 최대치

,,,

tab[n][m] = n번째 회사에 m원을 가지고 투자했을 때 얻을 수 있는 최대치

 

이 문제를 회사로, 주어진 금액으로 더 작은 문제를 쪼갠 뒤 해당 문제를 포함하는 상위 문제를 해결한다.

 

첫 회사에 m원을 가지고투자해서 얻을 수 있는 최대치를 얻고나면 2번째 회사에서 그 데이터를 가지고

1번째 회사에 투자한 돈에서 k만큼을 떼어 2번째 회사에 투자하는것이 더 가치 있는지 검사하는 식이다.

 

이런 방법으로 최종목적인 투자의 최대치를 얻을 수 있다.