Best Time to Buy and Sell Stock with Transaction Fee
여러가지 종류로 구성된 주식 구매와 관련된 문제중 하나이다.
1번의 거래만으로 벌 수 있는 최대의 가격, 무한번의 거래로 벌 수 있는 최대의 가격 등등 다양한 문제를 풀었지만, 매번 접근방법이 달랐기 때문에, 한번에 관통되는 접근방법을 정리하고자 한다.
참고: Leetcode Discussion
일단 기본적인 문제 해결 방법은 DP다. DP의 구성요소인
1. Overlapping subproblems
2. Optimal substructure
라는 것을 상기하며, 생각을 정리해보자.
그러면 DP 방식으로 접근하기 위해서는 '상태'에 초점을 맞추어야 한다. Finite State를 그리듯, 내가 나타낼 수 있는 상태가 무엇인지를 먼저 생각해보자.
예를들어 빈집털이 문제의 경우,
1. 내가 이 집을 털었을 때 얻을 수 있는 최대 수익
2. 이 집을 털지 않았을 때 얻을 수 있는 최대 수익
으로 두 상태를 나눌 수 있는데, 이렇게 해야하는 이유는, 실제 내가 행할 수 있는 action이 그 두가지이기 때문. 그렇지만 여기서도 action자체에 초점을 맞춘것은 아니다. 털거나, 안털거나 한 최종 상태에 초점을 둔거임..!
그럼 주식 문제에서의 action 뭐가 되는가? 라고 생각을 해 봤을때, 처음에 생각한 state는 그 때 주식을 사는 경우, 주식을 가지고 있는데 팔지 않는 경우, 주식을 파는 경우, 주식을 가지고 있지 않고, 사지도 않는 경우. 이렇게 4가지로 나누어서 접근을 하려고 했다. 근데, 각 경우가 너무 복잡하게 이루어져 있었고, 이전 단계에서 다음단계로 넘어오는 clue를 찾지 못하였었다.
action이 아닌 state에 초점을 맞춘다면?
아무쪼록,
1. ith day의 거래가 끝나고 내가 주식을 보유하고 있는 경우의 최대 수익
2. ith day의 거래가 끝나고 내가 주식을 보유하고 있지 않는 경우의 최대 수익
이 두단계로 나누어 본다면, 실제로 내가 어떤 액션을 하는지에는 초점을 맞추지 않은채로, 문제를 관통하는 state를 표현할 수 있다.
사실 이 단계가 가장 어려운 단계라고 생각한다. 물건을 사는 경우, 파는경우 등 행동에 초점을 맞추기 쉽지, 어떤 상태를 끌어낸다는 것은 연습이 많이 필요한 부분임
그리고 생각해야 하는 문제는 각 state의 base case가 무엇이 되는가? 인데, -1의 index라고 가정을 했을 때, 아무 주식도 가지고 있지 않으면(2번)? Profit은 0이 될 것. 그렇다면 시작도 안했는데 주식을 가지고 있으면(1번)? 불가능한 케이스..인데 이걸 0으로 두면 안됨. 불가능한 케이스이기 때문에, 가장 큰 disadvantage를 가지고 있어야 하고, '최대 수익'의 state를 저장함에 있어서 둘 수 있는 default value는 MIN_INT임.
그리고서 각 단계의 연결고리를 살펴보면,
상태1[i] = max(상태1[i-1], 상태2[i-1] - prices[i])
상태2[i] = max(상태2[i-1], 상태1[i-1] + prices[i])
가 됨을 알 수 있고, 이 상태별로 전환되는 과정에 action이 녹아있음을 안다.
Case1. (상태1[i] = 상태1[i-1])
주식을 구매한 상태에서 그걸 보유하고 있는게 이득인 상태.
Case2. (상태1[i] = 상태2[i-1] - prices[i])
가지고 있는 주식이 없는 상태에서 매수하는게 이득인 경우.
Case3. (상태2[i] = 상태2[i-1])
안산 상태로 가만히 있는게 이득인 경우
Case4. 상태2[i] = 상태1[i-1] + prices[i]
산 상태로 매도하는게 이득인 경우
사실.. 적고나면 쉬운데, 상태1의 transition과정에서 prices를 빼면서까지 maximum을 가지고 가는게 결과적으로 어떤 영향을 미칠지를 미리 생각해내는게 쉬운일은 아닌 것 같다.
배운점은,
- 하나 하나의 조건에 크게 신경쓰지 말고, action과 state를 생각해보기.
- state를 짠 뒤에, base case를 섬세하게 다루기
- 중간 단계에 대한 논리적인 확신을 믿고 진행하기
