주식 자동매매 시스템

파이썬을 이용한 주식 자동매매 시스템

이미지
파이썬을 이용한 주식 자동매매 시스템 INDEX 환경구축 키움증권 API - 연결테스트 키움증권 API - 계좌정보 조회 키움증권 API - 주문 키움증권 API - 종목정보 가져오기 포트폴리오 - 종목, 업종별 자산 포트폴리오 한국투자증권 API API reference 키움 OpenAPI+ 개발가이드 한국투자증권 OpenAPI 다운로드 및 가이드 Design https://www.design-seeds.com/in-nature/succulents/cacti-color-2/ https://create.piktochart.com/dashboard

[LeetCode] Python 문제해결과정 - Best Time to Buy and Sell Stock II

날마다 주식의 가격을 prices 배열로 주고, 주식을 사고팔아서 얻을 수 있는 최대 이익을 구하는 문제다. python을 사용해서 3번의 시도 끝에 풀었으며, 접근 방법과 솔루션에 대해 소개한다. 연관 문제로 Best Time to Buy and Sell Stock 1~3 등이 있다. 다양한 접근방법으로 풀어볼 수 있어서 흥미로웠던 문제이다.


122. Best Time to Buy and Sell Stock II

문제 링크

Solution 바로가기

 

First Approach (5분)

  • 문제 이해

  • 문제를 명확히 하기 위한 과정(Q&A)

  • 생각나는 알고리즘/자료구조

    주식을 사고파는데, 최대 1주만 보유할 수 있다. price가 최소일 때 사야 할 것 같다는 생각이 들었다.

    최소에서 팔 수 있을 때까지 날마다 diff profit을 저장해놓으면? DP를 적용해도 될 것 같은데 DP를 정확히 모르겠다.

    합이 더 크면 더 큰 노드로 옮겨가고, 작아질 때 멈추고 하면 될 것 같은데, 각 node 들의 차이를 합해 나가는 방법으로도 가능할 것 같다. 

     


First Solution(brute force)

class Solution:
    def calculate(self, prices: List[int], start: int) -> int:
        max_profit = 0
        max = 0
        if start < len(prices):
            for s in range(start, len(prices)):
                for e in range(start+1, len(prices)):
                    if prices[e] - prices[s] > 0:
                        max_profit = self.calculate(prices, e+1) + prices[e] - prices[s]
                    if max < max_profit:
                        max = max_profit

        return max
    
    def maxProfit(self, prices: List[int]) -> int:
        return self.calculate(prices, 0)

Result

Wrong Answer

First Aproach1: Brute Force - 재귀함수를 이용하는 방법을 Hint로 얻어 문제를 풀었다.

resolve >> e 를 start +1 로 했었는데, s+1로 수정

e는 항상 s보다 커야 하는데, 실수했다. 그런데 수정하고도 test case 몇 개는 통과했지만, Time Limit Exceeded 로 실패했다.



Second Solution

Approach #2 Peak Valley

valley[i], peak[i], valley[j], peak[j] 가 순서대로 있을 때, peak[i], valley[j]를 지나치면 valley[i], peak[j] 의 차이가 더 클 수 있지만 궁극적으로 A + B > C 라는 것을 명심하자.

A: peak[i] - valley[i]

B: peak[j] - valley[j]

C: peak[j] - valley[i]


Accepted Solution (57ms)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i = 0
        profit = 0
        while i < len(prices) - 1:
            while (i + 1) < len(prices) and prices[i] >= prices[i + 1]:
                i += 1
            valley = prices[i]
            while (i + 1) < len(prices) and prices[i] <= prices[i + 1]:
                i += 1
            peak = prices[i]
            profit += (peak - valley)

        return profit


Third Solution

Approach 3: Simple One Pass

위에서 peak, valley를 구하고 profit을 계산했지만, valley에서 peak까지 계속 더해도 max profit을 구할 수 있음. valley에서 peak까지의 경사면을 순서대로 이익을 더하면서 갈 수 있다. peak valley 의 값을 추적할 필요가 없고, 연속되는 숫자 간의 차이를 더해서 최대 이익만 알면되기 때문에.

Accepted Solution (155ms)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i = 0
        profit = 0
        while i < len(prices) - 1:
            if (i + 1) < len(prices) and prices[i] <= prices[i + 1]:
                profit += (prices[i+1] - prices[i])
            i += 1

        return profit

 

Corner Testcase

1. Time Limit Exceeded test case
[7,6,4,3,1]

Expected 0

Output 7

2.
[397,6621,4997,7506,8918,1662,9187,3278,3890,514,18,9305,93,5508,3031,2692,6019,1134,1691,4949,5071,799,8953,7882,4273,302,6753,4657,8368,3942,1982,5117,563,3332,2623,9482,4994,8163,9112,5236,5029,5483,4542,1474,991,3925,4166,3362,5059,5857,4663,6482,3008,3616,4365,3634,270,1118,8291,4990,1413,273,107,1976,9957,9083,7810,4952,7246,3275,6540,2275,8758,7434,3750,6101,1359,4268,5815,2771,126,478,9253,9486,446,3618,3120,7068,1089,1411,2058,2502,8037,2165,830,7994,1248,4993,9298,4846,8268,2191,3474,3378,9625,7224,9479,985,1492,1646,3756,7970,8476,3009,7457,8922,2980,577,2342,4069,8341,4400,2923,2730,2917,105,724,518,5098,6375,5364,3366,8566,8838,3096,8191,2414,2575,5528,259,573,5636,4581,9049,4998,2038,4323,7978,8968,6665,8399,7309,7417,1322,6391,335,1427,7115,853,2878,9842,2569,2596,4760,7760,5693,9304,6526,8268,4832,6785,5194,6821,1367,4243,1819,9757,4919,6149,8725,7936,4548,2386,5354,2222,8777,2041,1,2245,9246,2879,8439,1815,5476,3200,5927,7521,2504,2454,5789,3688,9239,7335,6861,6958,7931,8680,3068,2850,1181,1793,7138,2081,532,2492,4303,5661,885,657,4258,131,9888,9050,1947,1716,2250,4226,9237,1106,6680,1379,1146,2272,8714,8008,9230,6645,3040,2298,5847,4222,444,2986,2655,7328,1830,6959,9341,2716,3968,9952,2847,3856,9002,1146,5573,1252,5373,1162,8710,2053,2541,9856,677,1256,4216,9908,4253,3609,8558,6453,4183,5354,9439,6838,2682,7621,149,8376,337,4117,8328,9537,4326,7330,683,9899,4934,2408,7413,9996,814,9955,9852,1491,7563,421,7751,1816,4030,2662,8269,8213,8016,4060,5051,7051,1682,5201,5427,8371,5670,3755,7908,9996,7437,4944,9895,2371,7352,3661,2367,4518,3616,8571,6010,1179,5344,113,9347,9374,2775,3969,3939,792,4381,8991,7843,2415,544,3270,787,6214,3377,8695,6211,814,9991,2458,9537,7344,6119,1904,8214,6087,6827,4224,7266,2172,690,2966,7898,3465,3287,1838,609,7668,829,8452,84,7725,8074,871,3939,7803,5918,6502,4969,5910,5313,4506,9606,1432,2762,7820,3872,9590,8397,1138,8114,9087,456,6012,8904,3743,7850,9514,7764,5031,4318,7848,9108,8745,5071,9400,2900,7341,5902,7870,3251,7567,2376,9209,9000,1491,7030,2872,7433,1779,362,5547,7218,7171,7911,2474,914,2114,8340,8678,3497,2659,2878,2606,7756,7949,2006,656,5291,4260,8526,4894,1828,7255,456,7180,8746,3838,6404,6179,5617,3118,8078,9187,289,5989,1661,1204,8103,2,6234,7953,9013,5465,559,6769,9766,2565,7425,1409,3177,2304,6304,5005,9559,6760,2185,4657,598,8589,836,2567,1708,5266,1754,8349,1255,9767,5905,5711,9769,8492,3664,5134,3957,575,1903,3723,3140,5681,5133,6317,4337,7789,7675,3896,4549,6212,8553,1499,1154,5741,418,9214,1007,2172,7563,8614,8291,3469,677,4413,1961,4341,9547,5918,4916,7803,9641,4408,3484,1126,7078,7821,8915,1105,8069,9816,7317,2974,1315,8471,8715,1733,7685,6074,257,5249,4688,8549,5070,5366,2962,7031,6059,8861,9301,7328,6664,5294,8088,6500,6421,1518,4321,5336,2623,8742,1505,9941,1716,2820,4764,6783,906,2450,2857,7515,4051,7546,2416,9121,9264,1730,6152,1675,592,1805,9003,7256,7099,3444,3757,9872,4962,4430,1561,7586,3173,3066,3879,1241,2238,8643,8025,3144,7445,882,7012,1496,4780,9428,617,396,1159,3121,2072,1751,4926,7427,5359,8378,871,5468,8250,5834,9899,9811,9772,9424,2877,3651,7017,5116,8646,5042,4612,6092,2277,1624,7588,3409,1053,8206,3806,8564,7679,2230,6667,8958,6009,2026,7336,6881,3847,5586,9067,98,1750,8839,9522,4627,8842,2891,6095,7488,7934,708,3580,6563,8684,7521,9972,6089,2079,130,4653,9758,2360,1320,8716,8370,9699,6052,1603,3546,7991,670,3644,6093,9509,9518,7072,4703,2409,3168,2191,6695,228,2124,3258,5264,9645,9583,1354,1724,9713,2359,1482,8426,3680,6551,3148,9731,8955,4751,9629,6946,5421,9625,9391,1282,5495,6464,5985,4256,5984,4528,952,6212,6652,562,1476,6297,145,9182,8021,6211,1542,5856,4637,1574,2407,7785,1305,1362,2536,934,4661,4309,559,4052,1943,2406,516,4280,6662,2852,8808,7614,9064,1813,4529,6893,8110,4674,2427,2484,7237,3969,8340,1874,5543,7099,6011,3200,8461,8547,486,9474,9208,7397,9879,7503,9803,6747,1783,6466,9600,6944,432,8664,8757,4961,1909,6867,5988,4337,5703,3225,4658,4043,1452,6554,1142,7463,9754,5956,2363,241,1782,7923,7638,1661,5427,3794,8409,7210,260,8009,4154,692,3025,9263,2006,4935,2483,7994,5624,8186,7571,282,8582,9023,6836,6076,6487,6591,2032,8850,3184,3815,3125,7174,5476,8552,968,3885,2115,7580,8246,2621,4625,1272,1885,6631,6207,4368,4625,8183,2554,8548,8465,1136,7572,1654,7213,411,4597,5597,5613,7781,5764,8738,1307,7593,7291,8628,7830,9406,6208,6077,2027,833,7349,3912,7464,9908,4632,8441,8091,7187,6990,2908,4675,914,4562,8240,1325,9159,190,6938,3292,5954,2028,4600,9899,9319,3228,7730,5077,9436,159,7105,6622,7508,7369,4086,3768,2002,8880,8211,5541,2222,1119,216,3136,5682,4809,813,1193,4999,4103,4486,7305,6131,9086,7205,5451,2314,1287,528,8102,1446,3985,4724,5306,1355,5163,9074,9709,4043,7285,5250,2617,4756,1818,2105,6790,6627,2918,7984,7978,7021,2470,1636,3152,7908,8841,4955,222,6480,5484,4676,7926,5821,9401,3232,7176,916,8658,3237,1311,5943,8487,3928,7051,306,6033,3842,3285,8951,1826,7616,2324,648,9252,5476,8556,4445,6784]


 

Approach & Solution

Approach

  • Hint #1 Brute Force - 재귀함수
  • Hint #2 Peak Valley
  • Hint #3 Simple One Pass


Solution

class Solution:    
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)        
        profit = 0
        
        for i in range(1,n):
            if prices[i]>prices[i-1]:
                profit += prices[i]-prices[i-1]
                
        return profit


solution 코드를 보면, 푸는 방법이나 알고리즘은 동일하지만, index가 list 크기를 넘어가지 않도록(out of range 발생하지 않게) 하면서도 깔끔하게 작성되어 있다. 작은 차이지만 생각의 전환이 깔끔한 코드를 만드는 것 같다. 




Result

 

Spent Time

Result

1st

50min

Fail

2nd

30min

Accepted

3rd

10min

Accepted

최적화

-

-

Solution 학습

60min

-

Retry Date

2022/08/30

 


추가로, Brute Force - 재귀함수로 푸는 방식이 오히려 더 어렵게 느껴졌다. 재귀 호출하면서 최댓값을 갱신하는 방식이 머릿속에 잘 안 그려지는 듯하다.

이 블로그의 인기 게시물

Linux에서 CSV파일 사용방법

R에서 외부 데이터 이용하기 (Excel, csv)

[R 함수] aggregate, apply 사용 방법