[Algorithm] Dart로 풀어보는 주식 매수&매도 최적 시기

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.

Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

 

주어진 주식 가격 배열 prices 에서 주식을 여러 번 사고 팔 수 있으며, 최대 이익을 얻을 수 있는 방법을 찾는 문제입니다. 같은 날에 사고 팔 수는 없지만, 여러 번 사고 팔 수 있습니다. 즉, 가격이 오르는 경우에는 최대한 매도하여 이익을 얻을 수 있습니다.

 

 

나의 접근 방식

어떻게 최대 이익을 얻어야할까? 를 생각했습니다. List 첫번째값을 기준값으로 잡고 다음 값들과의 비교를 통해서 + 값을 구하고 그리고 + 값이 나오면 그 다음 값을 기준으로 다다음 값과의 비교를 통해서 + 값을 구하는 식의 재귀 형태로 찾아야하나를 고민했습니다. 이렇게되면 O의 몇제곱이 나올지 감이 안잡혔습니다. 그렇게 생각을 하다가 일단은 잘못된 방식이구나라고 생각을 했습니다만... 일단은 당장에 어떻게 풀어야할지 몰라서 해당 방식으로 구현을 했습니다만, 생각한 방식도 구현이 되지 않아서 포기...

 

 

그럼 어떻게 접근을 했어야했나 검색!!

연속된 두 날의 가격을 비교해서 가격이 상승하는 모든 구간에서 이익을 취하는 것 이 최대 이익을 보장합니다!

for (int i = 1; i < prices.length; i++) {
  if (prices[i] > prices[i - 1]) {
    totalProfit += prices[i] - prices[i - 1];
  }
}

 

이 알고리즘의 핵심은 "모든 상승 구간의 이익을 취한다" 는 것입니다.
예를 들어 [1,3,5]에서 1→5로 한 번에 팔든, 1→3, 3→5로 두 번 나누어 팔든 결과는 같습니다. 따라서 매일매일 상승분을 누적하는 것이 최적해가 됩니다. (시간복잡도: O(n), 공간복잡도: O(1) 의 방법)

 

 

이 문제를 풀기 위해서 알았으면 좋을 아이디어

- 그리디 알고리즘 (Greedy Algorithm)

// 매일매일 어제보다 오늘이 비싸면 → 어제 사서 오늘 팔기
if (today > yesterday) {
    profit += (today - yesterday);
}

 

- 배열 순회와 인접 원소 비교

 

- 수학적 직관 (연속된 상승 구간의 합 = 전체 상승폭)

연속 상승: [a, b, c] (a < b < c)
- 분할 거래: (b-a) + (c-b) = c-a
- 한 번 거래: c-a
→ 결과 동일! 하지만 분할이 더 유연함

 

그러나

문뜩 배열을 보고 주식이라는 문제를 봤을때는 더 큰 구간을 고려하고 싶은 마음이 듭니다.

예를 들어 [1, 2, 10, 3, 4]이면 1에서 사서 10에서 팔면 +9 아닌가? 왜 1→2(+1), 2→10(+8)로 나누지?

 

수학정 증명으로 보면 어떤 상승 구간 [a, b, c, d] (a < b < c < d)가 있다면

1. (b-a) + (c-b) + (d-c) = d-a

2. d-a

모두 같은 결과를 도출합니다. (수.학.적.증.명)

 

더불어서 [1, 5, 2, 6] 예를 들어보면 인접 방식으로 (5-1) + 0 + (6-2) = 4 + 0 + 4 = 8 구할 수 있고 다른 방식으로 구할 수 있겠으나 복잡한 구간 분석 필요하게 됩니다.

 

즉, 코드가 심플하도록 만든다고 하면 위에 언급한 코드 형태로 푸는게 베스트라고 합니다.