188. Best Time to Buy and Sell Stock IV

188. Best Time to Buy and Sell Stock IV

 

이 문제는 주어진 주식 가격 배열 prices에서 최대 k번의 거래를 통해 얻을 수 있는 최대 이익을 계산하는 문제입니다. 이 문제는 이전 문제들과 비슷하지만, 최대 k번의 거래를 허용한다는 점에서 확장된 형태입니다.

---

문제 이해

1. 거래 정의:
   • "거래"는 매수 후 매도를 의미합니다. 즉, 최대 k번의 거래를 할 수 있습니다.
2. 조건:
   • 거래는 동시에 진행할 수 없습니다. 즉, 매도 후에만 다시 매수할 수 있습니다.
   • 거래 횟수는 최대 k번입니다.
3. 목표:
   • 주어진 가격 배열에서 최대 k번의 거래를 통해 얻을 수 있는 최대 이익을 반환합니다.

class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        # 가격 배열이 비어있으면 거래를 할 수 없으므로 0 반환
        if not prices:
            return 0

        n = len(prices)  # 가격 배열의 길이 계산
        
        # 거래 횟수 k가 배열 길이의 절반 이상인 경우, 무제한 거래로 간주
        if k >= n // 2:
            return self.maxProfitUnlimited(prices)  # 무제한 거래 함수 호출

        # DP 테이블 초기화: (k + 1) x n 크기의 2차원 배열
        # dp[t][d]: t번의 거래로 0일부터 d일까지 얻을 수 있는 최대 이익
        dp = [[0] * n for _ in range(k + 1)]

        # 거래 횟수를 1부터 k까지 순회
        for t in range(1, k + 1):
            # max_diff: t-1번 거래를 완료하고 과거 날에 매수했을 때 얻을 수 있는 최대 차이
            max_diff = -prices[0]  # 첫 번째 날에 매수했다고 가정
            for d in range(1, n):  # 1일부터 n-1일까지 순회
                # 현재 날 d에서 t번의 거래로 얻을 수 있는 최대 이익 계산
                dp[t][d] = max(dp[t][d - 1], prices[d] + max_diff)
                # max_diff 갱신: 과거 날에 매수한 상태를 고려한 최대 차이 계산
                max_diff = max(max_diff, dp[t - 1][d] - prices[d])

        # k번의 거래로 마지막 날(n-1)까지 얻을 수 있는 최대 이익 반환
        return dp[k][n - 1]

    # 무제한 거래 시 최대 이익을 계산하는 함수
    def maxProfitUnlimited(self, prices):
        # 초기 이익은 0
        profit = 0
        # 가격 배열 순회
        for i in range(1, len(prices)):
            # 전날보다 가격이 상승한 경우, 이익을 누적
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        # 누적된 이익 반환
        return profit

 

요약

이 코드는 주어진 가격 배열과 최대 거래 횟수를 기반으로, 동적 계획법을 사용해 효율적으로 최대 이익을 계산합니다. 거래 횟수가 많아지면 별도로 처리하여 성능을 최적화합니다.

 

 

거래 횟수가 배열 길이의 절반 이상인 경우, 무제한 거래로 간주?? 왜??

 

좋은 질문입니다! 이 부분은 알고리즘을 최적화하기 위해 특별한 경우를 다룬 것입니다. 이를 이해하려면 문제의 조건과 무제한 거래의 의미를 살펴보아야 합니다.

---

조건 설명

• 주어진 문제에서는 최대 k번의 거래를 할 수 있다고 명시되어 있습니다.
• 하지만, **거래 횟수 k**가 배열의 길이(n)의 절반 이상인 경우, k ≥ n/2 라면, k라는 제한이 사실상 의미가 없어집니다.
  • 이유는 매수 후 매도를 완료하려면 최소 2개의 날이 필요하기 때문입니다.
  • 따라서, 주어진 배열에서 가능한 거래 횟수는 최대 n/2번이 됩니다.

---

예제

거래 횟수 제한이 의미가 없는 경우:

입력:

• k=10, prices=[3,2,6,5,0,3]
• 배열 길이 n=6
• 가능한 최대 거래 횟수는 n/2=3번.
• 따라서, k=10 이라고 해도 실제로는 최대 3번 거래밖에 할 수 없습니다.
• 즉, k는 무제한처럼 동작합니다.

 

캐슁으로..

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        dp = {} # k 번 거래 해야 함 (date, k, buying) -> 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 = dfs(i+1, k-1, not buying) + prices[i]
                dp[(i, k, buying)] = max(sell, cooldown)

            return dp[(i, k, buying)]

        return dfs(0, k, True)

 

속도 개선을 위해 interational DP로 변형

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        """
        dp = {} # k 번 거래 해야 함 (date, k, buying) -> 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 = dfs(i+1, k-1, not buying) + prices[i]
                dp[(i, k, buying)] = max(sell, cooldown)

            return dp[(i, k, buying)]

        return dfs(0, k, True)
        """

        """
        # 같은 로직을 interational DP로 바꾸면
        """
        if not prices:
            return 0

        n = len(prices)

        """
        DP 배열 초기화
        - dp[n][k][buying] 배열을 위해
        - [0]*2 : buying, sell 두가지        
        - k와 n 범위가 +1 주의: 
            k 는 거래 이므로, 거래는 1부터 k 까지.
            date는 다음 거래가 i+1 이므로, 염두해두고 +1 하는것이 indexing 에 편리
        """
        dp = [[[0] * 2 for _ in range(k+1)] for _ in range(n+1)]

        # bottom up 으로 계산해야 함        
        for i in range(n - 1, -1, -1):  # 날짜
            for kk in range(1, k + 1):   # 남은 거래 횟수                  
                cooldown_when_sell = dp[i+1][kk][0] # 그냥 있는 거                
                sell = dp[i+1][kk-1][1] + prices[i] # 판매
                dp[i][kk][0] = max(sell, cooldown_when_sell) # 판매 상태

                cooldown_when_buy = dp[i+1][kk][1] # 그냥 있는 거                
                buy = dp[i+1][kk][0] - prices[i] # 구매
                dp[i][kk][1] = max(buy, cooldown_when_buy) # 구매 상태               

        return dp[0][k][1] #  첫 번째 날부터 시작, 최대 k번 거래, 구매 가능 상태