Best Time to Buy and Sell Stock

이번 포스트에서는 Best Time to Buy and Sell Stock 대표 문제를 풀어보겠습니다.

 

 

이 시리즈 문제는 Stock을 사고 팔아서 최대 이익을 내는 문제로 다양한 조건이 들어가면서 난이도가 달라집니다.

 

전반적으로 Sliding Window, Dynamic Programming 기법을 사용하여 풀 수 있습니다.

코딩 테스트 시에 연계해서 나오기 좋은 문제이므로 알아두면 좋습니다.

 

Stock 문제의 가장 기본적인 원리는 팔기 전에 반드시 구매해야 한다는 점입니다. 따라서 Stock을 현재 가지고 있지 않다면 아무리 값이 올라도 판매할 수 없습니다. 또한 거래라고 하면 사고 파는 것이 한 사이클 완료된 경우를 의미합니다. 저는 stock을 사는 경우 거래를 시작한다고 생각하고 문제를 풀었습니다.

 

한가지 팁을 드리면, 문제를 푸실 때 점화식 일반화를 해보시는 것이 좋습니다. i번째에서의 최대 이익을 stock을 가진 상태와 모두 판매한 상태로 나누고, 그 값을 어떻게 구할지 생각해보면 쉽게 문제를 푸실 수 있습니다.

 

1. Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock - LeetCode

풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 최솟값을 추적하기 위해서 변수를 하나 정의합니다.
        # 초기값은 상당히 큰 수를 지정하여, 첫번째 원소에서 바로 min_val이 업데이트 될 수 있도록 합니다.
        # 다른 방법으로는 첫 원소의 값으로 지정하셔도 됩니다.
        min_val = 1e9
        
        # 최대 이익을 저장하기 위한 변수를 정의합니다.
        ans = 0
        
        # 배열을 순회하면서 최대 이익을 구하고, 최솟값을 업데이트합니다.
        for price in prices:
            ans = max(ans, price - min_val)
            min_val = min(min_val, price)
        return ans

첫번째 문제는 가장 싼 값에 사서 비싼 값이 파는 경우를 찾아야 합니다. 다만 Stock의 특성상 사기 전에 파는 것은 불가합니다. 즉, prices[i]에 판다고 가정했을때, 구매는 반드시 [0, i-1] 에서 진행해야 합니다. 

 

따라서 아래와 같은 알고리즘으로 풀이를 진행합니다.

1. 배열을 순회하면서 각 위치에서 판매한다고 가정합니다.

2. 현재 위치 이전에 있던 price 중에서 가장 싼 값과의 차액을 구합니다.

3. 지금까지의 최솟값과 현재값의 최소를 구하여 저장합니다.

 

 

2.Best Time to Buy and Sell Stock II

Best Time to Buy and Sell Stock II - LeetCode

풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        # stock을 가지고 있을 때의 수익을 저장할 변수를 정의합니다.
        # 초기값은 상당히 작은 값을 넣어서 스톡이 없는 상태에서 수익이 나올 수 없는 경우를 표현합니다.
        with_stock = -1e9
        
        # stock이 없는 상태에서의 수익을 저장할 변수를 정의합니다
        # stock이 없는 상태이기 때문에 초기값은 0이 됩니다.
        without_stock = 0
        
        
        for price in prices:
            # 배열을 순회하면서 stock을 먼저 구매합니다.
            # 구매시의 최대값을 먼저 구하는 이유는 산 후에 같은 날 팔 수 있기 때문입니다.
            # 만약 해당 일자에 값이 엄청 싸면, 기존에 들고 있던 stock(with_stock)을 버리고 현재 stock을 사는 것이 유리합니다. (without_stock - price).
            with_stock = max(with_stock, without_stock - price)
            
            # 구매 여부를 결정한 후에는 판매하는 케이스를 결정합니다.
            # 만약 해당 일자에 값이 엄청 비싸면, 기존에 들고 있는 stock을 판 것과 기존에 아무것도 들고 있지 않은 경우를 비교하여 큰 값을 취합니다.
            # 만약 이날 구매를 했다면, 판매하는 것이 더 손해이기 때문에 기존에 아무것도 없는 상태가 유지됩니다.
            without_stock = max(without_stock, with_stock + price)
            
        # 최댓값은 stock을 손에 들지 않는 경우입니다.
        return without_stock

 

두번째 문제에서는 원하는 만큼 사고 팔 수 있습니다. 따라서 매번 최소 금액에 사서 최대 금액에 팔아서 이익을 구해야합니다. 따라서 stock을 가지고 있을 때의 최대 이익(= 최소로 stock을 사는 경우), stock을 가지고 있지 않을 때의 최대 이익(=최대로 stock을 파는 경우)을 계산하면 됩니다.

 

i번째 날에 stock을 보유한 상태에서의 최대 이익 = max(i-1번째 날에 stock을 보유한 상태에서의 최대이익, i-1번째 날에 stock을 모두 거래한 상태에서 i번째날 stock 구매)

 

i번째 날에 stock을 가지고 있지 않을 때의 최대 이익 = max(i-1번째 날에 stock을 모두 거래한 상태에서의 최대이익, i-1번째 날에 stock을 가지고 있다가 i 번째 날에 stock 판매)

 

이때 최댓값은 stock을 가지고 있지 않은 상태에서의 최대 이익을 반환하시면 됩니다. 왜냐하면 stock을 굳이 마지막 날에 들고 있을 필요가 없기 때문입니다.

 

3. Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III - LeetCode

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        
        # with_stock[i][j] = j번째 날에 i번째 stock을 소유한 상태에서의 최대 이익
        with_stock = [[-1e9 for _ in range(n+1)] for _ in range(3)]
        
        # without_stock[i][j] = j번째 날에 i번째 stock까지 거래를 마친 상태에서의 최대 이익
        without_stock = [[0 for _ in range(n+1)] for _ in range(3)]
        for i in range(1, 3):
            for j in range(1, n+1):
                
                # i번째 stock을 j번째 날에 가지고 있을때 최대 이익은 아래 둘 중 하나의 경우입니다.
                # 1) j-1번째 날에 i번째 stock을 가지고 있을 때의 최대이익(즉, j번째 날에는 아무 거래도 하지 않음)
                # 2) j-1번째 날에 i-1번째까지 stock을 전부 거래하고 나서 j번째 날에 stock을 구입하는 경우
                # prices 배열에서 j-1을 사용하는 이유는 j번째 날의 실제 인덱스는 j-1이기 때문입니다.
                with_stock[i][j] = max(with_stock[i][j-1], without_stock[i-1][j-1] - prices[j-1])
                
                #  j번째 날에 i번째 stock까지 거래를 완료한 상태의 최대 이익은 아래 둘 중 하나의 경우입니다.
                # 1) j-1번째 날에 i번째 stock까지 거래를 완료한 상태의 최대이익(즉, j번째 날에는 아무 거래도 하지 않음)
                # 2) j-1번째 날에 i번째 stock을 보유한 상태에서 j번째 날에 stock을 판매하는 경우
                without_stock[i][j] = max(without_stock[i][j-1], with_stock[i][j-1] + prices[j-1])
        
        return without_stock[2][n]

세번째 문제는 최대 2번까지만 거래를 할 수 있습니다. 따라서 거래의 횟수까지 추적을 해야합니다. 거래 횟수는 stock을 살때 증가시킵니다. 로직은 두번째 문제와 같습니다.

 

4. Best Time to Buy and Sell Stock IV

Best Time to Buy and Sell Stock IV - LeetCode

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        
        # with_stock[i][j] = j번째 날에 i번째 stock을 소유한 상태에서의 최대 이익
        with_stock = [[-1e9 for _ in range(n+1)] for _ in range(k+1)]
        
        # without_stock[i][j] = j번째 날에 i번째 stock까지 거래를 마친 상태에서의 최대 이익
        without_stock = [[0 for _ in range(n+1)] for _ in range(k+1)]
        for i in range(1, k+1):
            for j in range(1, n+1):
                
                # i번째 stock을 j번째 날에 가지고 있을때 최대 이익은 아래 둘 중 하나의 경우입니다.
                # 1) j-1번째 날에 i번째 stock을 가지고 있을 때의 최대이익(즉, j번째 날에는 아무 거래도 하지 않음)
                # 2) j-1번째 날에 i-1번째까지 stock을 전부 거래하고 나서 j번째 날에 stock을 구입하는 경우
                # prices 배열에서 j-1을 사용하는 이유는 j번째 날의 실제 인덱스는 j-1이기 때문입니다.
                with_stock[i][j] = max(with_stock[i][j-1], without_stock[i-1][j-1] - prices[j-1])
                
                #  j번째 날에 i번째 stock까지 거래를 완료한 상태의 최대 이익은 아래 둘 중 하나의 경우입니다.
                # 1) j-1번째 날에 i번째 stock까지 거래를 완료한 상태의 최대이익(즉, j번째 날에는 아무 거래도 하지 않음)
                # 2) j-1번째 날에 i번째 stock을 보유한 상태에서 j번째 날에 stock을 판매하는 경우
                without_stock[i][j] = max(without_stock[i][j-1], with_stock[i][j-1] + prices[j-1])
        
        return without_stock[k][n]

네번째 문제는 세번째 문제에서 횟수를 동적으로 변경한 경우입니다. 따라서 2로 고정했던 배열을 K개로 늘리고 K*N만큼 배열을 순회하면 구하실 수 있습니다.

 

5. Best Time to Buy and Sell Stock with Cooldown

Best Time to Buy and Sell Stock with Cooldown - LeetCode

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        
        # with_stock은 i번째 날에 stock을 가지고 있는 상태에서의 최대 이익입니다.
        with_stock = [-1e9 for _ in range(n+1)]
        
        # without_stock은 i번째 날에 stock을 모두 판매한 상태에서의 최대 이익입니다.
        without_stock = [0 for _ in range(n+1)]
        
        for i in range(1, n+1):
            with_stock[i] = with_stock[i-1]
            
            # 만약 첫날이라면 cooldown이 없기 때문에 예외처리를 합니다. 즉, 첫날에는 바로 구매할 수 있도록 합니다.
            if i == 1:
                with_stock[i] = max(with_stock[i], without_stock[i-1] - prices[i-1])
                
            # 첫날을 제외하고 구매할때는 cooldown이 필요하기 때문에 i-2번째 날에 판매를 완료한 상태에서 구매를 하는 경우를 비교합니다.
            elif (i > 1):
                with_stock[i] = max(with_stock[i], without_stock[i-2] - prices[i-1])
            
            # 판매는 cooldown이 없기 때문에 i-1번째 날에 가지고 있는 stock을 i번째에 판매하는 경우를 비교합니다.
            without_stock[i] = max(without_stock[i-1], with_stock[i-1] + prices[i-1])
            
        return without_stock[n]

 

---

 

지금까지 stock을 사고 파는 시리즈 문제를 풀어보았습니다.

도움이 되셨다면 자주 나오는 Two Sum 시리즈도 한 번 보시는 것을 추천드립니다.

Two Sum