2021-11-20 주식 최대 수익 구하기

 

1. BruteForce

 

def max_profit(stock_list):
    max_profit_so_far = stock_list[1] - stock_list[0]
    
    for i in range(len(stock_list)):
        for j in range(i+1,len(stock_list)):
            max_profit_so_far = max(max_profit_so_far, stock_list[j] - stock_list[i])
    return max_profit_so_far

하나하나 보면서 모든 경우를 살펴보면 된다. O(n^2)

 

2. So_Far

 

def max_profit(stock_list):
    max_profit_so_far = stock_list[1] - stock_list[0]
    
    min_so_far = min(stock_list[0], stock_list[1])
    for i in range(2, len(stock_list)):
        max_profit_so_far = max(max_profit_so_far, stock_list[i] - min_so_far)
        
        min_so_far = min(min_so_far, stock_list[i])
    return max_profit_so_far

주식은 최저에 사서 최고점에 판다. 우리가 현재 인지할수 있는 지점은 최고점이다. 따라서 최고점은 우리가 정하는 것이 아니라 시간이 정하는 것이다.

 

그래서 우리가 컨트롤 할 수 있는 것은 최솟값을 정허는 것이므로 최소값을 담을 변수를 하나 만든다.

 

그리고 현재 주식을 팔면 최대 수익인지 확인하고,

 

현재 주식이 최소가격인지 확인한다.

 

그러면 O(n)의 시간복잡도로 간단해진다.

 

2021-11-20