동적 기획의 주식 매매

주로 동적 기획의 방식으로 알고리즘 문제를 해결하는 것을 설명한다. 비록 일부 문제도 다른 더욱 빠른 방법으로 해결할 수 있지만 본 편은 동적 기획의 사상을 주목한다.
Best Time to Buy and Sell Stock
한 번만 매매하여 최대 이윤을 구할 수 있다
이동한 후 수조를 두루 훑어보고 i일째 팔면 얻을 수 있는 최대 이윤, 즉 i （ ） - 1~i-1 （ ）을 구한다.
상태 전환 방정식:

max_profit[i] = max(price[i] - min_buy_price[i-1], max_profit[i-1])

min_buy_price[i] = min(price[i], min_buy_price[i-1])

import unittest

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) < 2:
            return 0

        max_profit = 0 
        min_buy_price = prices[0]

        for price in prices:
            if price > min_buy_price:
                max_profit = max(max_profit, price - min_buy_price)
            else:
                min_buy_price = min(min_buy_price, price)
        
        return max_profit

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.s = Solution()

    def test_one(self):
        input = [7, 1, 5, 3, 6, 4]
        self.assertEqual(self.s.maxProfit(input), 5)
    
    def test_two(self):
        input = [7, 6, 4, 3, 1]
        self.assertEqual(self.s.maxProfit(input), 0)

if __name__ == "__main__":
    unittest.main()

Best Time to Buy and Sell Stock II
여러 차례 매매를 허용하여 최대 이윤을 구하다
i일에는 2가지 상태가 있다. 주식 보유own[i], 주식 미보유no_own[i]이면 그 상태 방정식은 다음과 같다.

당일이 지나면 수중에 주식을 보유하는 조건하에서 ①당일 매입한 경우.② 당일 운용하지 않고 기존에 매입한 경우.own[i] = max(own[i-1], no_own[i-1] - price[i])

당일이 지난 후 수중에 주식을 보유하지 않은 조건하에서 두 가지 상황이 있다. ①당일에 팔린 경우.② 당일 조작 없이 이전에 판매한 경우.no_own[i] = max(own[i-1] + price[i], no_own[i-1])

상태 전환 방정식:

own[i] = max(own[i-1], no_own[i-1] - price[i])

no_own[i] = max(own[i-1] + price[i], no_own[i-1])

import unittest

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """

        if len(prices) < 2:
            return 0

        own = [0] * len(prices)
        no_own = [0] * len(prices)
        own[0] = -prices[0]

        for i in range(1, len(prices)):
            own[i] = max(own[i-1], no_own[i-1] - prices[i])
            no_own[i] = max(no_own[i-1], own[i] + prices[i])

        return no_own[-1]

class TestSolution(unittest.TestCase):
    def test_one(self):
        prices = [7,1,5,3,6,4]
        s = Solution()
        print(s.maxProfit(prices))

    def test_two(self):
        prices = [1, 2, 3, 4, 5]
        s = Solution()
        print(s.maxProfit(prices))


if __name__ == "__main__":
    unittest.main()

Best Time to Buy and Sell Stock III
최대 두 번의 임의 매매로 최대 이윤을 구하다
i일에는 2가지 상태가 있는데 k는 k차 왕복 거래라고 한다. 주식 보유own[k][i], 주식 보유no_own[k][i]가 없으면 그 상태 방정식은 다음과 같다.

당일이 지나면 수중에 주식을 보유하는 조건하에서 두 가지 상황이 있다. ①당일은 제k차 윤회 매입이다.② 당일 조작하지 않아 앞서 k번째로 매입한 경우.own[k][i] = max(own[k][i-1], no_own[k-1][i-1] - price[i])

당일이 지난 후에 수중에 주식을 보유하지 않은 조건에서 두 가지 상황이 있다. ①당일은 제k차 라운드 매각이다. 즉, 이전의 제k차 라운드 매입을 토대로 계산한다.② 당일 조작하지 않고 앞서 k차 라운드로 판매한 경우.no_own[k][i] = max(own[k][i-1] + price[i], no_own[k][i-1])

상태 전환 방정식:

own[k][i] = max(own[k][i-1], no_own[k-1][i-1] - price[i])

no_own[k][i] = max(own[k][i-1] + price[i], no_own[k][i-1])

import unittest
from pprint import pprint

class Solution:
    def maxProfit(self, prices):
        if len(prices) < 2:
            return 0

        length = len(prices)

        own = [[0]*(length) for i in range(3)]
        no_own = [[0]*(length) for i in range(3)]

        own[1][0] = own[2][0] = -prices[0]

        for k in range(1,3):
            for j in range(1, length):
                own[k][j] = max(own[k][j-1], no_own[k-1][j-1] - prices[j])
                no_own[k][j] = max(no_own[k][j-1], own[k][j-1] + prices[j])
        return no_own[-1][-1]

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.s = Solution()

    def test_one(self):
        input = [3, 3, 5, 0, 0, 3, 1, 4]
        self.assertEqual(self.s.maxProfit(input), 6)
    
    def test_two(self):
        input = [1, 2, 3, 4, 5]
        self.assertEqual(self.s.maxProfit(input), 4)

if __name__ == "__main__":
    unittest.main()

Best Time to Buy and Sell Stock IV
최대 k회 임의 매매, 최대 이윤 추구
마찬가지로 k가 비교적 클 수 있기 때문에 공간을 절약하기 위해 우리는 k%2를 이용하여 공간을 절약한다. 왜냐하면 매번 k차 거래는 지난번 거래와 관련이 있기 때문이다.단지 위의 최적화만으로는 부족하다. k가 클 수 있기 때문에 k>=len(prices)//2만 하면 Best Time to Buy and Sell Stock II의 문제로 바뀌어 많은 계산량을 감소시켰다.

import unittest

class Solution:
    def maxProfit(self, k, prices):
        if len(prices) < 2:
            return 0
        
        length = len(prices)

        if k >= length//2:
            own = [0] * length
            no_own = [0] * length
            own[0] = -prices[0]

            for i in range(1, length):
                own[i] = max(own[i-1], no_own[i-1] - prices[i])
                no_own[i] = max(no_own[i-1], own[i] + prices[i])

            return no_own[-1]

        own = [[0]*(length) for i in range(2)]
        no_own = [[0]*(length) for i in range(2)]

        own[0][0] = own[1][0] = -prices[0]

        for k in range(0, k):
            k = k % 2
            own[k][0] = -prices[0]
            for j in range(1, length):
                own[k][j] = max(own[k][j-1], no_own[k-1][j-1] - prices[j])
                no_own[k][j] = max(no_own[k][j-1], own[k][j-1] + prices[j])
        return max(no_own[0][-1], no_own[1][-1])

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.s = Solution()

    def test_one(self):
        input = [2, 4, 1]
        self.assertEqual(self.s.maxProfit(2,input), 2)
    
    def test_two(self):
        input = [3, 2, 6, 5, 0, 3]
        self.assertEqual(self.s.maxProfit(2, input), 7)

    def test_three(self):
        input = [1, 2]
        self.assertEqual(self.s.maxProfit(1, input), 1)
if __name__ == "__main__":
    unittest.main()

Best Time to Buy and Sell Stock with Cooldown
임의의 거래는 가능하나 주식을 판 다음날은 거래가 허용되지 않는다
i일에는 2가지 상태가 있다. 주식 보유own[i], 주식 미보유no_own[i]이면 그 상태 방정식은 다음과 같다.

당일이 지나면 수중에 주식을 가지고 있는 조건에서 ①당일 매입한 경우 조건이 제한되어 i-1 이전에만 팔 수 있다.② 당일 운용하지 않고 기존에 매입한 경우.own[i] = max(own[i-1], no_own[i-2] - price[i])

당일이 지난 후 수중에 주식을 보유하지 않은 조건하에서 두 가지 상황이 있다. ①당일에 팔린 경우.② 당일 조작 없이 이전에 판매한 경우.no_own[i] = max(own[i-1] + price[i], no_own[i-1])

상태 전환 방정식:

own[i] = max(own[i-1], no_own[i-2] - price[i])

no_own[i] = max(own[i-1] + price[i], no_own[i-1])

import unittest

class Solution:
    def search(self, nums, target):
        if len(nums) == 0:
            return -1

        l = 0
        h = len(nums) - 1

        while l < h:
            m = l + (h-l)//2
            if nums[m] <= target:
                l = m + 1
            elif nums[m] >= target:
                h = m
        
        pos = -1 
        if nums[l] > target:
            pos = l

        return pos

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.s = Solution()

    def test_one(self):
        input = [-1, 0, 3, 3, 5, 9, 12]
        self.assertEqual(self.s.search(input, 3), 4)
    
    def test_two(self):
        input = [-1, 0, 3, 3, 5, 9, 12]
        self.assertEqual(self.s.search(input, 2), 2)

    def test_three(self):
        input = [0]
        self.assertEqual(self.s.search(input, 0), -1)

if __name__ == "__main__":
    unittest.main()

Best Time to Buy and Sell Stock with Transaction Fee
임의로 여러 건 거래할 수 있지만, 매번 거래할 때마다 일정한 비용을 지불해야 한다fee
i일에는 2가지 상태가 있다. 주식 보유own[i], 주식 미보유no_own[i]이면 그 상태 방정식은 다음과 같다.

당일이 지나면 수중에 주식을 보유하는 조건하에서 ①당일 매입한 경우.② 당일 운용하지 않고 기존에 매입한 경우.own[i] = max(own[i-1], no_own[i-1] - price[i])

당일이 지난 후 수중에 주식을 보유하지 않은 조건하에서 두 가지 상황이 있다. ①당일 매도한 경우 이때 거래비를 지불해야 한다.② 당일 조작 없이 이전에 판매한 경우.no_own[i] = max(own[i-1] + price[i] - fee, no_own[i-1])

상태 전환 방정식:

own[i] = max(own[i-1], no_own[i-1] - price[i])

no_own[i] = max(own[i-1] + price[i] - fee, no_own[i-1])

import unittest

class Solution:
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """

        length = len(prices)

        if len(prices) < 2:
            return 0

        last_own = -prices[0]
        last_no_own = 0

        for i in range(1, length):
            own = max(last_own, last_no_own - prices[i])
            last_no_own = max(last_no_own, last_own + prices[i] - fee)
            last_own = own
        
        return last_no_own

class TestSolution(unittest.TestCase):
    def setUp(self):
        self.s = Solution()

    def test_one(self):
        input = [1, 3, 2, 8, 4, 9]
        self.assertEqual(self.s.maxProfit(input, 2), 8)

    def test_two(self):
        pass

if __name__ == "__main__":
    unittest.main()

총결산
처음에 이 문제들을 풀 때 어디서부터 손을 대야 할지 모르겠지만 이 몇 문제의 훈련을 거친 후에 대부분의 동태 계획에 대해 분석할 수 있다. 상태 방정식이 유도된 후에 초기 값을 확정하면 최종 결과를 얻을 수 있다.