작성계기
11월 10일, LeetCode 오늘의 문제를 풀다가 느낀점을 기록하기 위해서 포스팅을 작성하였다. 결론을 먼저 말하면 한가지 접근 방법을 고집하지 말자는 것을 느꼈다. 코딩을 하다보면 몇번씩 이런 생각이 드는데 오늘은 기록을 하는 것이 좋겠다고 생각했다.
오늘의 문제는 "Best Time to Buy and Sell Stock II"이라는 문제인데, 일자별 주식 가격이 1차원 배열로 주어지고, 그것을 바탕으로 매매를 했을 때 얻을 수 있는 최대 수익을 구하는 문제였다. 추가적으로 주식은 한번에 한 주만 가지고 있을 수 있다는 조건이 있다. 무슨 얘기냐하면 어느날 주식을 하나 사서 갖고 있다면 이 주식을 팔지 않으면 주식을 살 수 없다는 말이다.
- 정확한 문제 설명은 LeetCode 페이지를 참고
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
접근방법 ①
참고! 접근방법 ①은 Time Limit Exceeded가 떠서 통과가 안된다.
일단 코딩 문제를 풀 때, 나는 문제 설명을 읽고 그 다음 예시로 주어진 Case를 확인한 후에, 제한 사항을 확인한다.
문제를 보자마자, 가장 단순하게 모든 경우를 다 따져보는 것을 생각해보았다. 그러니까 첫날부터 주식을 사는 경우와 사지 않는 경우로 시작하는 것이다. 말로 설명하는 것보다 일종의 순서도로 나타내는 것이 편할 것 같아 그려보았다.
그림은 3일까지밖에 그리지 않았지만 일수가 늘어날 수록 경우의 수가 많아지는 것을 알 수 있을 것이다. 그래서 이 접근 방법을 생각한 후에 제한 사항을 보았다. 배열의 크기 제한이 30,000이기 때문에 모든 경우의 수는 2^30000-1가지인 것을 예상할 수 있고, 이 경우의 수를 모두 따져보는 것은 시간이 매우 오래 걸릴 것이고 당연히 정답이 아닐 것이다.
그래서 모든 경우를 따져보기보다는 따지지 않아도 되는 경우는 아예 브랜치를 잘라버렸다.(순서도가 Tree 모양을 띄고 있어서 이렇게 표현해보았다. 쉽게 말하면 더 따져볼 필요가 없는 경우는 후에 계산을 생략했다는 말이다.)
내가 생각한 더 이상 계산을 할 필요가 없어지는 때를 정리해보면 아래와 같았다.
- 주식을 구매한 날의 가격보다 주식의 가격이 낮을 때는 판매를 할 이유가 없다. (daytobuy라는 변수를 활용했다.)
- N일째까지의 최대 이익을 연산을 하면서 기록해놓는다. 그리고 N일째 이익을 계산할 때, 미리 기록해놓은 최대 이익보다 작으면 연산을 멈춘다.(이 때 주식을 갖고 있는지 아닌지 구분이 필요하여 함수의 파라미터로 check라는 Bool값을 사용하였다.)
class Solution {
private:
vector<int> maximum;
int daytobuy;
public:
void maxProfit(vector<int>& prices, int day, int profit, bool check /*hold stock(true) or not(false)*/ )
{
// 마지막 날까지 계산했을 때
if(day == prices.size())
{
if(profit > maximum[day-1])
maximum[day-1] = profit;
return;
}
// 더 이상 연산이 필요 없을 때
if(profit < 0 && !check)
return;
if(profit < maximum[day] && !check)
return;
if(profit > maximum[day])
{
maximum[day] = profit;
}
if(check) // hold stock
{
maxProfit(prices, day+1, profit, check); // do nothing
if(prices[daytobuy] < prices[day]){
maxProfit(prices, day+1, profit+prices[day], !check); // sell
}
}
else // not hold stock
{
maxProfit(prices, day+1, profit, check); // do nothing
int prev = daytobuy;
daytobuy=day;
maxProfit(prices, day+1, profit-prices[day], !check); // buy
daytobuy= prev;
}
}
int maxProfit(vector<int>& prices) {
int answer = 0;
maximum = vector<int>(prices.size(), -10001);
maxProfit(prices, 0, 0, 0);
answer = maximum[prices.size() - 1];
return answer;
}
};그래서 작성한 코드는 위와 같다. 주어진 테스트 케이스는 모두 통과를 하였고, 자체적으로 만든 테스트 케이스도 통과하여 제출을 했는데, 배열의 길이가 1,000개 정도가 넘어가자 'Time Limit Exceeded"가 떴다.
그래서 코드를 짠 후에도 1시간 정도, 브랜치를 더 자를 수 있는 아이디어가 있을까 고민해보았다.
접근방법 ②
결국 아이디어가 잘 생각이 나질 않았고, 떠올라도 연산 시간에 그렇게 크게 영향을 미칠 것 같지 않았다. 그래서 다른 사람들의 해결방법을 보기 위해서 Discuss 탭에 들어가서 다른 사람들의 풀이를 보았다.
풀이를 보자마자 '아 접근방법 ①로 풀면 안되는구나'라는 생각이 들었다. 왜냐하면 그래프를 보자마자 새로운 아이디어가 떠올랐기 때문이다.
위는 문제 풀이에 포함된 그래프이다.
그냥 나의 느낀점..
안타까운 것은 내가 문제를 보자마자 주어진 Input 값을 단순히 [1,7,2,3,6,7,6,7]과 같이 수열로만 볼 것이 아니라 머리속으로 그래프를 그려보았다면 한가지 방법을 고집하지 않았을 것이란 것이다.
코딩을 해보면서 많이 느끼지만 데이터를 다각적으로 볼 필요가 있고 그럴 수 있는 능력은 참 중요한 것 같다.
예전 같았으면 이런 상황에서 단순한 생각도 하지 못한 것에 대해 자괴감을 느꼈을 것이다. 하지만 코딩을 해보다 보니 생각의 전환을 하는 것은 생각보다 쉽지 않고 그런 능력은 하루 아침에 얻어지지 않는다. 다만 분명한 것은 아직 초보이긴하지만 컴퓨터를 처음 공부했을 때보다는 지금 코딩을 더 잘한다. 그러니까 지금처럼 조금씩이라도 코딩을 해보려고 지속적으로 노력하고 훈련한다면 분명 나아질 것이라고 믿는다.
그래프를 다시 보면 뭔가 느껴지는 것이 있을 것이다. 설명을 보지 않아도 A+B+C의 값이 D의 값과 같다는 것을 눈치챘다.
어렵게 바꿔 말해보면 주식 가격 배열(수열)의 어떤 구간 내의 수열이 단조증가하면 그 구간에서의 최대 수익은 수열의 모든 원소에 대해서 원소(주식 가격)와 그 다음 원소의 차이값의 합과 같다.
이를 코드로 옮기면 아래와 같다. Leetcode의 'archit91'란 사람의 코드를 인용했다.
class Solution {
public:
int maxProfit(vector<int>& P) {
int profit = 0;
for(int i = 1; i < size(P); i++)
if(P[i] > P[i-1]) // yesterday was valley, today is peak
profit += P[i] - P[i-1]; // buy yesterday, sell today
return profit;
}
};훨씬 짧은 코드로 Time Limit Exceeded 없이 모든 테스트 케이스가 통과되는 것을 확인할 수 있다.
