123. Best Time to Buy and Sell Stock III ★★★

123. Best Time to Buy and Sell Stock III

 

문제 설명

이 문제는 주어진 주식 가격 배열 prices를 기반으로 최대 두 번의 거래를 통해 얻을 수 있는 최대 이익을 찾는 문제입니다.

• 조건:
  1. 최대 두 번의 거래: 두 번의 매수/매도만 가능하며, 두 번째 거래는 첫 번째 거래가 완료된 후에만 가능합니다.
  2. 동시 거래 금지: 주식을 보유한 상태에서 다시 매수할 수 없습니다. 즉, 먼저 매도 후에 새로운 거래를 시작해야 합니다.
  3. 최대 이익 반환: 두 번의 거래를 통해 얻을 수 있는 최대 이익을 반환합니다.

풀이 방법

접근 방식

이 문제는 동적 계획법(DP) 또는 **상태 추적(State Tracking)**으로 해결할 수 있습니다.

각각의 거래 상태를 정의하고, 이를 기반으로 계산합니다.

 

상태 추적 법

상태 정의

• 4가지 주요 상태:
  1. first_buy: 첫 번째 거래를 위한 최소 비용.
  2. first_profit: 첫 번째 거래의 최대 이익.
  3. second_buy: 두 번째 거래를 위한 최소 비용.
  4. second_profit: 두 번째 거래의 최대 이익.

---

알고리즘

1. 초기값 설정:
   • first_buy = float('inf')
   • first_profit = 0
   • second_buy = float('inf')
   • second_profit = 0
2. 배열 순회:
   • first_buy: 현재까지 최소 가격으로 첫 번째 매수를 고려.
   • first_profit: 첫 번째 매도를 통해 얻을 수 있는 최대 이익.
   • second_buy: 첫 번째 거래 이익을 포함해 두 번째 매수를 고려.
   • second_profit: 두 번째 매도를 통해 얻을 수 있는 최대 이익.
3. 최종 결과:
   • second_profit이 두 번의 거래를 통해 얻을 수 있는 최대 이익.

BEST Solution

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
    	"""
        # 최소 2번 거래 해야함
        # profit을 얻으려면, buy 는 싸게, sell 은 비싸게 
        # price 가 작은걸 찾아서 사야하므로 buy 초기값은 아주 큰값으로
        # profit 은 초기값을 0으로
        """
        buy1 = float("inf")  # 첫 번째 거래의 최소 구매 비용
        profit1 = 0          # 첫 번째 거래의 최대 이익
        buy2 = float("inf")  # 두 번째 거래의 최소 구매 비용 (첫 번째 이익 반영)
        profit2 = 0          # 두 번째 거래의 최대 이익

        for price in prices:
            buy1 = min(buy1, price)  # 첫 번째 거래에서 최소 구매 비용 갱신
            profit1 = max(profit1, price - buy1)  # 첫 번째 거래에서 최대 이익 갱신

            buy2 = min(buy2, price - profit1)  # 두 번째 거래의 유효 구매 비용 계산
            profit2 = max(profit2, price - buy2)  # 두 번째 거래의 최대 이익 갱신

        return profit2  # 최종 최대 이익 반환

 

 

코드 설명

1. first_buy:
   • 현재까지 가장 낮은 가격을 저장합니다.
   • 예: min(first_buy, price)
2. first_profit:
   • 첫 번째 매도 시 얻을 수 있는 최대 이익.
   • 예: max(first_profit, price - first_buy)
3. second_buy:
   • 첫 번째 거래 이익을 고려한 후 두 번째 매수를 위한 최소 비용.
   • 예: min(second_buy, price - first_profit)
4. second_profit:
   • 두 번째 거래로 얻을 수 있는 최대 이익.
   • 예: max(second_profit, price - second_buy)

요약

이 접근법은 각 상태를 추적하여 효율적으로 문제를 해결합니다. 단순히 두 번의 거래 상태를 유지하면서, 최대 이익을 계산합니다. 이를 통해 시간과 공간 모두에서 최적화를 이룹니다.

 

 

 

접근 방법 (DP)

 

DP 방식에서는 두 번의 거래를 각각 처리하며, 각 시점에서 가능한 최대 이익을 계산합니다. 이를 위해 다음 두 가지를 추적합니다:

1. left[i]:
   • 첫 번째 거래에서, 0일부터 i일까지 가능한 최대 이익.
2. right[i]:
   • 두 번째 거래에서, i일부터 마지막 날까지 가능한 최대 이익.

최종적으로, **left[i] + right[i]**의 최대값을 계산하여 두 번의 거래를 통해 얻을 수 있는 최대 이익을 구합니다.

 

class Solution:
    def maxProfit(self, prices):
        if not prices:
            return 0
        
        n = len(prices)
        left = [0] * n  # 첫 번째 거래의 최대 이익
        right = [0] * n  # 두 번째 거래의 최대 이익

        # Step 1: Calculate `left` array
        min_price = prices[0]
        for i in range(1, n):
            min_price = min(min_price, prices[i])
            left[i] = max(left[i - 1], prices[i] - min_price)

        # Step 2: Calculate `right` array
        max_price = prices[-1]
        for i in range(n - 2, -1, -1):
            max_price = max(max_price, prices[i])
            right[i] = max(right[i + 1], max_price - prices[i])

        # Step 3: Combine results from `left` and `right`
        max_profit = 0
        for i in range(n):
            max_profit = max(max_profit, left[i] + right[i])

        return max_profit

 

코드 설명

1. left 배열 계산:
   • min_price를 갱신하면서, 해당 시점까지의 최대 이익을 left[i]에 저장합니다.
2. right 배열 계산:
   • max_price를 갱신하면서, 해당 시점부터 마지막 날까지의 최대 이익을 right[i]에 저장합니다.
3. 최종 결과 계산:
   • 각 시점 iii에서 두 번의 거래를 나눠 진행할 수 있으므로, left[i] + right[i]의 최대값이 최종 결과가 됩니다.

요약

DP 방식은 배열을 두 번 순회하여 가능한 두 번의 거래를 나눠서 처리합니다.

이는 상태 추적법과 달리 모든 가능성을 배열로 저장하여 직관적으로 문제를 해결합니다.

DP 방식은 더 많은 메모리를 사용하지만, 상태를 명시적으로 추적할 수 있다는 장점이 있습니다.

 

DP 캐슁으로..

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 최소 2번 거래 해야함
        # profit을 얻으려면, buy 는 싸게, sell 은 비싸게 
        # price 가 작은걸 찾아서 사야하므로 buy 초기값은 아주 큰값으로
        # profit 은 초기값을 0으로
        dp = {} # DP 캐슁을 위한 해쉬맵 (date, state) = max profit

        def dfs(i, k, buying):
            if i >= len(prices) or k == 0:
                return 0

            if (i, k, buying) in dp:
                return dp[(i, k, buying)]

            cooldown = dfs(i+1, k, buying) # 아무것도 하지 않는

            if buying:
                buy = dfs(i+1, k, not buying) - prices[i]
                dp[(i, k, buying)] = max(buy, cooldown)
            else: # sell
                sell = dfs(i+1, k-1, not buying) + prices[i] 
                dp[(i, k, buying)] = max(sell, cooldown)

            return dp[(i, k, buying)]

        return dfs(0, 2, True)  # Day 0부터 시작하며, 최대 2번 거래 가능

sell 할 때만 k-1을 하는 이유