Leetcode - Best Time to Buy and Sell Stock 2

23 Oct 2024 in Algorithm

알고리즘 공부

Daily Leetcode

• 📀 Greedy Solution
• 🪫 Dynamic Programming Solution

문제 링크

문제는 해석하면 이렇다. 이전과 다르게 다양한 날짜에 사고팔려고 한다. 다만 주식은 한번에 최대 한 개만 가지고 있어야 하며 동일 날짜에 매도 후 매수가 가능하다.

이런 상황에서 가장 큰 수익을 구하면 된다.

📀 Greedy Solution

문제를 생각해보면 계속 사고팔고를 진행해야되는 것 같다. 그렇다면 내가 내일보다 싸게 매수한다면 항상 이득이 아닐까?

예를 들어 [1,2,1,2,8] 데이터를 본다고 할 때 답은 1에 매수 2에 매도 / 1에 매수 8에 매도 로 총 8의 수익을 올릴 수 있다.

하지만 위 답은 결국 1에 매수 2에 매도 / 1에 매수 2에 매도 / 2에 매수 8에 매도 와 같으며 해당 이득 역시 8이 되게 된다.

즉 최적의 매도 타이밍을 찾는 것이 아니라 다음날보다만 싸다면 매수를 하면 되는 것이다. 이를 아래 코드처럼 표현할 수 있다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        days = len(prices)

        profit = 0
        for day in range(days-1):
            if prices[day] < prices[day+1]:
                profit += (prices[day+1] - prices[day])
        return profit

• TC : O(N)

• SC : O(1)

면접관이 다른 풀이를 떠올려보라 한다.

🪫 Dynamic Programming Solution

주식 매매에는 두 개의 액션을 취할 수 있다. 관망 혹은 매수. 그렇다면 내가 특정 날짜에 매수했을 때, 혹은 매수하지 않고 관망만 할 때를 DP로 처리할 수 있다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        days = len(prices)
        STAY, HOLD  = 0, 1

        dp = [[0 for _ in range(days)] for _ in range(2)]
        dp[HOLD][0] = -prices[0]

        for day in range(1, days):
            dp[STAY][day] = max(dp[STAY][day-1], dp[HOLD][day-1]+prices[day])
            dp[HOLD][day] = max(dp[HOLD][day-1], dp[STAY][day-1]-prices[day])

        return dp[STAY][days-1]

STAY는 관망이며 HOLD는 주식을 보유한다는 것이다. 따라서 첫째날 dp[HOLD]는 주식을 매수했기에 음수값으로 취해준다.

그 다음부터는 본격적으로 DP가 시작된다.

• 관망하는 경우 : 전날에 관망했을 때 얻은 수익, 보유 중인 주식을 매도하여 수익을 내는 경우 중 큰 값을 저장한다.
• 매수하는 경우 : 전날에 보유햇을 때 얻은 수익, 어제까지 관망해서 얻은 수익에서 오늘 주식을 매수하여 빠진 값 중 큰 값을 저장한다.

마지막으로 리턴할 때는 무조건 매도를 해야되기에 STAY index를 보게 된다.

• TC : O(N)

• SC : O(N)

이런 상황에서는 크게 DP가 와닿지는 않는 것 같다.